+0  
 
0
540
3
avatar

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
avatar
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
avatar
0

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

Guest Jul 29, 2018
 #3
avatar+25225 
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$.} \)

 

laugh

 Jul 30, 2018

4 Online Users

avatar