17. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

SzamelmSzig > DaniVeloxKidolgozas >

• Teljes és redukált maradékrendszer, φ-függvény definíciója. Euler-Fermat-tétel , kis Fermat-tétel. Euklideszi algoritmus.

Ha a mod m maradékosztályok mindegyikéből kiválasztunk egy tetszőleges elemet, a keletkező számhalmazt mod m _teljes maradékrendszer_nek nevezzük. A mod m maradékosztályok közül azokból, melyek minden eleme relatív prím m-hez kiveszünk egyet-egyet, a keletkező számhalmazt mod m _redukált maradékrendszer_ének nevezzük. _φ(m)_: az m-nél kisebb, m-hez relatív prímek száma

• Tétel*: _Euler-Fermat_: Ha m>1 tetszőleges egész szám és a tetszőleges olyan szám, melyre (a,m)=1, akkor a^φ(m)≡1 (mod m).

• Tétel*: _„kis” Fermat_: Tetszőleges p prímszámra és tetszőleges a egész számra a^p≡a (mod p)

• Bizonyítás*:
  

1. p|a =>  0≡ap≡a≡0 (mod p)

2. nem p|a => (p,a)=1 =>{Euler Fermat}=> aφ(p)≡1 (mod p) 
 φ(p)=p-1, így ap-1≡1 (mod p), azaz ap≡a (mod p)

_Euklideszi algoritmus_: a,b számok legnagyobb közös osztójának kiszámításához.
a = h₁b+m₁ (0≤m₁<b)
b = h₂m₁+m₂ (0≤m₂<m₁)
m₁ = h₃m₂+m₃(0≤m₃<m₂)
és így tovább.
Az eljárás akkor ér véget, ha nincs az osztásnak maradéka, vagyis m_n-2=h_nm_n-1. m_n-3=h_n-1m_n-2+ m_n-1=(h_n-1h_n+1)m_n-1,… a és b is m_n-1 többszöröse lesz,→m_n-1 közös osztója a-nak és b-nek. Megfordítva, a és b tetszőleges közös osztója m₁-nek is osztója…m_n-1-nek is. Tehát m_n-1= (a,b). Másképp: (a,b)=(b,m₁)=(m₁,m₂)=…=(m_n-2,m_n-1)=m_n-1→a és b közös osztóinak halmaza megegyezik legnagyobb közös osztójuk osztóinak halmazával.

-- SzaMa - 2005.09.17.