Reszta z dzielenia Kamil: Witam mam takie zadanie. Reszta dzielenia liczby 3²017 przez 7 wynosi ? Da się zrobić tą zadanie nie używając kongurencji ?

Adamm:

	1008 n
32017=3*91008=3*(7+2)1008=3*∑n=01008		7n21008−n

wszystkie elementy sumy oprócz n=0 są podzielne więc sprawdzamy tylko dla n=0

	336 n
3*21008=3*8336=3*(7+1)336=3*∑n=0336		7n

ponownie, jedynie dla n=0 mamy wyraz niepodzielny zatem reszta wynosi 3

Adamm: użyłem tutaj dwumianu Newtona

n k
	to symbol Newtona

n k		n!
	=
		k!(n−k)!

Adamm: inaczej można tak (o wiele prościej) 3²⁰¹⁷=3^6*336+1 z twierdzenia Fermata 3⁶≡1 (mod 7) 3⁶≡1 (mod 7) ⇒ 3^6*336≡1 (mod 7) 3≡3 (mod 7) ∧ 3^6*336≡1 (mod 7) ⇒ 3^6*336+1≡3 (mod 7)

Adamm: lub tak 3²⁰¹⁷=3*9¹⁰⁰⁸≡3*2¹⁰⁰⁸=3*8³³⁶≡3 (mod 7)