Question

100 PKT!!!! Dana jest liczba pierwsza p większa od 3 oraz liczba całkowita a. Wykazać, że liczby [tex]a^{p^{2}}[/tex] i a dają tę samą resztę z dzielenia przez 5.

Answer 1

Odpowiedź:

Szczegółowe wyjaśnienie:

Podzielmy problem na przypadki ze względu na resztę z dzielenia liczby a przez 5.

a) a = 5k, oczywiste

b) a = 5k + 1, w zasadzie też, bo

c) a = 5k + 4

wiemy, że p jest nieparzyste, więc p^2 też, zapiszmy p^2 jako (2j + 1)

d,e)

a = 5k + 2

a^2 daje resztę 4

a^3 daje 3

a^4 daje 1

a^5 daje 2

widać, że potęgi powtarzają się co 4

a = 5k + 3

a^2 daje resztę 4

a^3 daje 2

a^ 4 daje 1

a^5 daje 3

tu też potęgi powtarzają się co 4

W obu przypadkach takie same reszty dają potęgi: 5, 9, 13 ... Łączy je to, że  przy dzieleniu przez 4 dają resztę 1. Jeśli uda się pokazać, że p^2 zawsze daje resztę 1 przy dzieleniu przez 4 to będzie koniec dowodu.

Rozpatrzmy więc przypadki ze względu na resztę z dzielenia liczby p przez 4

a) p = 4h - zawsze dzieli się przez 4, więc p nie jest pierwsza i nie spełnia warunków zadania, odrzucamy

b) p = 4h + 2, zawsze dzieli się przez 2, odrzucamy

c) p = 4h + 1, wtedy p^2 = 16h^2+8h+1, daje resztę 1 przy dzieleniu przez 4

d) p = 4h+3, wtedy p^2 = 16h^2+24h+9, też daje resztę 1

Wiemy więc, że p^2 daje resztę 1 przy dzieleniu przez 4, co kończy dowód