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.

Guest Jul 28, 2018

#1**0 **

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.**

Guest Jul 29, 2018

#3**0 **

**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$.} \)

heureka Jul 30, 2018