contestada

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.

Respuesta :

Medunno13

Part (a)

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

[tex]10^{6} \equiv 1 \pmod{7} \\ \\ \therefore 10^{6}-1 \equiv 0 \pmod{7}[/tex]

Part (b)

Note that

[tex]10^{12n}-1=(10^n)^{12}-1 \equiv 0 \pmod{13}[/tex]

Since

[tex]1 = 1001 - 1000[/tex]

and

[tex]-1 \equiv 1000 \pmod{1001}[/tex]

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

[tex]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}[/tex]