Let A=111111 and B=142857. Find a positive integer N with six or fewer digits such that N is the multiplicative inverse of AB modulo 1,000,000.
Let A=111111 and B=142857. Find a positive integer N with six or fewer digits such that N is the multiplicative inverse of AB modulo 1,000,000.
[111,111 x 142,857] x M mod 1,000,000 =1, solve for M
LCM[111,111, 142,857] = 999,999
GCD[111,111, 142,857] =15,873
M =999,999 / 15,873 =63 - is the multiplicative inverse of AB mod 1,000,000.
+26367 Let A=111111 and B=142857. Find a positive integer N with six or fewer digits such that
N is the multiplicative inverse of AB modulo 1,000,000.
\(\begin{array}{rcll} \text{Let} \\ & A=111111 \\ \text{and} \\ & B=142857 \\ \end{array}\)
\(\begin{array}{rcll} A\text{ and } B \text{ are factors of } 999999. \\ & 9A=999999 \\ \text{and} \\ & 7B=999999 \\ \end{array}\)
\(\begin{array}{rcll} A\text{ and } B \text{ modulo } 1000000. \\ & 9A \equiv -1 \pmod{1000000} \\ \text{and} \\ & 7B \equiv -1 \pmod{1000000} \\ \end{array}\)
\(\begin{array}{rcll} \text{Multiply these equations: } \\ & (9A)(7B) &\equiv& (-1)(-1) \pmod{1000000} \\ & (AB) (9\cdot 7) &\equiv& 1 \pmod{1000000} \\ & (AB)\underbrace{(63)}_{=(AB)^{-1}} &\equiv& 1 \pmod{1000000} \\ \end{array}\)
\(\text{So $N=\boxed{63}$ is the multiplicative inverse to $AB$ modulo $1000000$.} \)
