+0  
 
0
107
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.

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

Guest 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+20680 
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

heureka  Jul 30, 2018

10 Online Users

avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.