Question 16

Number Theory Level pending

Let $A=111111$ and let $B=142857.$ Find the smallest positive integer $N$ such that $N$ is the multiplicative inverse of $AB\text{ mod }1,000,000.$

1 solution

Michael Diao
Jun 25, 2014

Notice that $7B=999,999 \equiv -1 \pmod{1,000,000}$ . Thus, by modular arithmetic,

$\frac{999,999\times 7B}{111,111}$

is what we desire.

The expression turns out to cancel nicely, and we are left with

$\boxed{63}.$