Pokušaću da na intuitivnom nivou predstavim značenje kongruencija. Kada kažeš da je a kongruentno b po modulu n to u stvari znači da pri deljenju a sa n dobijaš ostatak b.

Evo par primera.

5 je kongruentno 1 po modulu 4.
111 je kongruentno 11 po modulu 100.
123 je kongruentno 3 po modulu 120.

S tim što recimo može da bude i ovako:
9 kongruentno -1 po modulu 5.

Sasvim logično, kongruencije se koriste kod dokazivanja deljivosti i traženja ostataka pri deljenju.

Odrediti ostatak pri deljenju 2^30 sa 13.
To zapisujemo ovako 2^30kongruentno n (mod 13)
i dalje neumem da nastavim zbunjuje me ovaj eksponent 30.

Treba primetiti da je . Pošto je , a 64 je kongruentno -1 po modulu 13 (65=5*13) obe strane možemo stepenovati sa 5, pa je polazni broj kongruentan sa -1 po modulu od 13.

Dakle eksponent ne predstavlja problem, kongruencije se uglavnom i koriste u zadacima takvog tipa. Treba samo znati pravilo da ako je a kongruentno b po modulu n, tada je i kongruentno po modulu n.

Odrediti ostatak od po modulu .

OK, prvo treba znati da važe sledeći zakoni:

1. Ako je , onda je .

2. Ako je i , onda je i .

3. Ako je , onda je .

4. Za ma koji prost broj i ceo broj takav da je .

Dakle, , pa je .