16. Számelméleti kongruenciák és tulajdonságaik

Question 1

Számelméleti kongruencia:

Answer 1

• Legyen $m∈ \Z$ tetszőleges(rögzített) egész szám, $m \neq 0$. Ekkor tetszőleges $a,b∈ \Z$ számokra legyen $a≡b (mod$ $m)$ pontosan akkor ha $m|a$-b. m-et a kongruencia modulusának nevezzük. $≡_m$ pontosabb elnevezése számelméleti kongruencia, hiszen a geometriai egybevágóság sok élő nyelven szintén kongruencia, és van általános algebrai kongruencia is.

Question 2

Számelméleti kongruencia tulajdonságok

Answer 2

• Legyen $m∈ \Z$ tetszőleges(rögzített) egész szám, $m \neq 0$. Ekkor tetszőleges $a,b∈ \Z$ számokra legyen $a≡b (mod$ $m)$ pontosan akkor ha $m|a$-b. m-et a kongruencia modulusának nevezzük. $≡_m$ pontosabb elnevezése számelméleti kongruencia, hiszen a geometriai egybevágóság sok élő nyelven szintén kongruencia, és van általános algebrai kongruencia is.

Tulajdonságok:

• $m|n$ esetén $a≡_nb$-ből következik $a≡_mb$, de megfordítva (általában) nem igaz.
• Tetszőleges $m∈ Z$, $m \neq 0$ számra, valamint bármely $a,b,c,d∈ \Z$ számokra

Ha $a≡_mb$ és $c≡_md$

Akkor $a±c≡_mb±d$ és $a·c≡_mb·d$

• Ha $a≡_nb$ és $m|n$ akkor $a≡_mb$
• Ha $ac≡bc$ $mod(n)$ akkor $a≡b (mod \frac {n} {lnko(c, n)})$
• Ha $ac=bc$ $(mod$ $n)$ és $lnko(n,c)=1$, akkor $a≡b$ $(mod$ $n)$

Question 3

Maradék osztályok:

Answer 3

• Jelölés: Jelölje $\Z_n$ a $(mod$ $n)$ összes maradékok halmazát:

$\Z={0,1,…,n-1}$

• Teljes maradékrendszer: Az n darab tetszőleges ${a_1, .., a_n}⊆ \Z$ számot teljes maradékrendszernek hívjuk (mod n), ha az ai számok (mod n) maradékai az összes $\Z_n$-beli maradékot kiadják, mindegyiket pontosan egyszer.
• Def: Tetszőleges $n∈ Z(n \neq 0)$ számra $\Z_n$-nek n-hez relatív prím elemeinek halmazát redukált maradékrendszernek nevezzük (mod n) és $\Z^∗_n$ -al jelöljük. Tetszőleges $n∈ Z(n \neq 0)$ számra jelölje $ϕ(n)$ a $(mod$ $n)$ redukált maradékosztályok számát, azaz legyen $ϕ(n)=|\Z^∗_n |$.
• Tetszőleges $n∈ \N$ szám esetén $ϕ(n)$ jelölje az n-nél kisebb, n-hez relatív prím számok számát, azaz legyen

$ϕ(n) = |{a < n : lnko(a, n) = 1}|$.

Ezt a függvényt Euler-féle ϕ függvénynek nevezzük.

Question 4

Lagrange tétele:

Answer 4

• Ha G egy véges csoport és H egy részcsoportja G-nek, akkor H elemeinek száma osztja G elemeinek számát, azaz $|H|$ $|$ $|G|$.

Question 5

Euler “számelméleti” tétele:

Answer 5

• Ha $a,m∈ \Z$ tetszőleges, és $lnko(a,m)=1$, akkor $a≡1$ $(mod$ $m)$.

Question 5

Euler “számelméleti” tétele:

Answer 5

• Ha $a,m∈ \Z$ tetszőleges, és $lnko(a,m)=1$, akkor $a≡1$ $(mod$ $m)$.

Question 6

Fermat tétele:

Answer 6

• Ha $p∈ P$ prím és $a∈ \Z$, $p|a$ tetszőleges, akkor $a^{p−1} ≡1$ $(mod$ $p)$.

Question 7

Nagy kitevőjű hatványok:

Answer 7

• Adottak $m,k,n ∈ \Z$ nagy (több százjegyű) számokKérdés: $n^k ≡?$ $(mod$ $m)$$n^2 ≡a$$n^4 ≡ a^2 ≡b$$n^8 ≡ b^2 ≡c$lépések száma: $l=?$$2^l ≤ k < 2^{l+1}$, $l≈ log_a(k)$összesen: $2-log(k)$.