+0

number theory

0
326
3

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.

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.

Jul 29, 2018
#2
0

Thanks so much! I would've never thought of using that way... Thanks again

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.}$$ Jul 30, 2018