17. tétel

A VIK Wikiből
A lap korábbi változatát látod, amilyen (vitalap) 2012. október 21., 22:15-kor történt szerkesztése után volt. (Új oldal, tartalma: „{{GlobalTemplate|Infoalap|SzamElmTetelA17}} SzamelmSzig > DaniVeloxKidolgozas > *Teljes és redukált maradékrendszer, φ-függvény definíciója. …”)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)
Ugrás a navigációhoz Ugrás a kereséshez

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 ap≡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 = h1b+m1 (0≤m1<b)
b = h2m1+m2 (0≤m2<m1)
m1 = h3m2+m3(0≤m3<m2)
és így tovább.
Az eljárás akkor ér véget, ha nincs az osztásnak maradéka, vagyis mn-2=hnmn-1. mn-3=hn-1mn-2+ mn-1=(hn-1hn+1)mn-1,… a és b is mn-1 többszöröse lesz,→mn-1 közös osztója a-nak és b-nek. Megfordítva, a és b tetszőleges közös osztója m1-nek is osztója…mn-1-nek is. Tehát mn-1= (a,b). Másképp: (a,b)=(b,m1)=(m1,m2)=…=(mn-2,mn-1)=mn-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.