Potęga siódemki
-
Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Potęga siódemki
Udowadniamy, że dla pewnego \(\displaystyle{ k\in \NN^+}\) zajdzie \(\displaystyle{ 7^k\equiv 1\pmod{1000}}\).
Popatrzmy na liczby
\(\displaystyle{ 7^1, \ 7^2, \ldots 7^{1001}}\)
Z zasady szufladkowej Dirichleta wynika, że któreś dwie z tych liczb dają taką samą resztę z dzielenia przez \(\displaystyle{ 1000}\), niech będą to \(\displaystyle{ 7^a, \ 7^b}\) i niech \(\displaystyle{ a>b}\).
Wówczas \(\displaystyle{ 1000}\) dzieli liczbę \(\displaystyle{ 7^a-7^b=7^b(7^{a-b}-1)}\).
Ponieważ zaś \(\displaystyle{ \NWD(7^b, 1000)=1}\), to \(\displaystyle{ 1000}\) dzieli liczbę \(\displaystyle{ 7^{a-b}-1}\), czyli
\(\displaystyle{ 7^{a-b}\equiv 1\pmod{1000}}\), c.n.d.
Popatrzmy na liczby
\(\displaystyle{ 7^1, \ 7^2, \ldots 7^{1001}}\)
Z zasady szufladkowej Dirichleta wynika, że któreś dwie z tych liczb dają taką samą resztę z dzielenia przez \(\displaystyle{ 1000}\), niech będą to \(\displaystyle{ 7^a, \ 7^b}\) i niech \(\displaystyle{ a>b}\).
Wówczas \(\displaystyle{ 1000}\) dzieli liczbę \(\displaystyle{ 7^a-7^b=7^b(7^{a-b}-1)}\).
Ponieważ zaś \(\displaystyle{ \NWD(7^b, 1000)=1}\), to \(\displaystyle{ 1000}\) dzieli liczbę \(\displaystyle{ 7^{a-b}-1}\), czyli
\(\displaystyle{ 7^{a-b}\equiv 1\pmod{1000}}\), c.n.d.