Kongruentnost

#fax #math #ds1 [deo poglavlja "celi brojevi"]

Def. Neka su i je prirodan broj. Tada je kongruentno sa po modulu () ako

( i daju isti ostatak pri deljenju na )

Stav. je relacija ekvivalencije na

Stav. Ako i , onda važi

  3. , za svako

Stav. Broj je deljiv sa 3 akko zbir njegovih cifara je deljiv sa 3.

,
su cifre broja





Tada:

Oznaka.

Primer. Odrediti ostatak pri deljenju sa .
Treba naći tako da *


**

* U zadacima nikada ne morate računati veće stepene. Uvek je moguće faktorisati i napraviti ugneždeni stepeni (na primer ; )
** Obično je cilj imati najmanji broj po modulu (u ovom slučaju u intervalu ), onda je lakše množiti.

Stav. i . Tada

Dokaz:

Jednačina oblika


— Diofantova jednačina, koja ima rešenja ako


Možemo podeliti diofantovu jednačinu sa :
(ima isti skup rešenja kao i polazna jednačina)

I metoda:
Rešavanjem diofantove jednačine dobijamo rešenje u obliku

II metoda:
U prebrojavanjem treba naći koji zadovoljava jednačinu
Tada rešenje je

Rešenja iz : rešenja
(Ako je rešenje iz onda rešenja iz su
)

Primeri

Kineska teorema o ostacima

Teorema. Ako onda sistem jednačina

ima rešenja.
Ako je je jedno rešenje sistema onda su sva rešenja oblika

Rešavanje sistema:
Rešavamo prvu jednačinu dobijamo
Ubacujemo to u drugu jednačinu, rešavamo po dobijamo: , gde je *
Zatim vračamo:
Ubacujemo to u treću jednačinu, rešavamo po dobijamo: , gde je *
Zatim vračamo:
i tako dalje, dok nećemo dobiti

(* ne morate da učite ove razlomke, te brojevi se dobijaju sami, rešavanjem kongruencija)

Primer 1
Primer 2

Ojlerova teorema

Def. Neka je prirodan broj, tada skup je Ojlerov skup.
je Ojlerova funkcija.

Stav. je Abelova grupa.

  • Zatvorenost operacije: i
    (*)
  • Asocijativnost i komutativnost su očigledni
  • Neutral je ,
  • Inverz: za (*)
    odakle , , — inverz od

Primer:




Teorema.

Stav. je prost, tada

Iz osnovne teoreme aritmetike:
Tada


Teorema (Ojlerova). i su prirodni brojevi i .
Tada

Dokaz:
(*)
Na osnovu posledice

Posledica (mala Fermaova teorema). , je prost, .
Tada

Primer

Vilsonova teorema

Teorema. je prost akko