Question

Problem 10

(a) Using Fermat's little theorem, show that 999 999 is divisible by 7.
(b) A number has digits that are all 9 and is divisible by 13. Show that
it is also divisible by 1001.

Answer 1

Part (a)

Note 999999=1000000-1. By Fermat's little theorem, since 100000=10⁶,

`10^(6) \equiv 1 \pmod{7} \\ \\ \therefore 10^(6)-1 \equiv 0 \pmod{7}`

Part (b)

Note that

`10^(12n)-1=(10^n)^(12)-1 \equiv 0 \pmod{13}`

Since

`1 = 1001 - 1000`

and

`-1 \equiv 1000 \pmod{1001}`

10³ is its own inverse modulo 1001, meaning that:

`10^3 x \equiv 1 \pmod{1001} \implies x=10^3 \\ \implies 10^(12n)=(10^3 \cdot 10^3)^(2n) \equiv 1 \pmod{1001} \\ \\ \implies 10^(12n)-1 \equiv 0 \pmod{1001}`