BSz1 Jegyzet

3. Tétel:

Euler-féle φ-függvény, képlet a meghatározására (csak prímhatvány esetre bizonyítva). Redukált maradékrendszer, Euler-Fermat-tétel, kis Fermat-tétel. Két kongruenciából álló kongruenciarendszer megoldása (konkrét, megadott példán).

3.1. Kongruencia és közös osztók (1.5.1. Állítás)

1.5.1. Állítás:

Ha $a \equiv b \pmod m$ teljesül, akkor $(a, m) = (b, m)$.

Részletes Bizonyítás:

A feltétel szerint $a \equiv b \pmod m$, ami a definíció alapján azt jelenti, hogy $m \mid a - b$. Ebből következik, hogy létezik olyan $k$ egész szám, amelyre: $b = a + k \cdot m$

1. Legyen $d = (a, m)$. Tudjuk, hogy egy $d$-vel osztható szám bármely többszöröse, illetve ilyenek összege is osztható $d$-vel.

2. Mivel $d$ a legnagyobb közös osztója $a$-nak és $m$-nek, ezért a $d \mid a$ és $d \mid m$ oszthatóságokból következik, hogy $d \mid k \cdot m$ is teljesül.

3. Ebből adódik, hogy $d$ osztja az összegüket is: $d \mid a + k \cdot m = b$.

Ezek szerint $d$ közös osztója $b$-nek és $m$-nek is. Mivel egy közös osztó nem lehet nagyobb, mint a legnagyobb közös osztó, ezért: $d = (a, m) \le (b, m)$

Mivel $a$ és $b$ szerepe az állításban teljesen szimmetrikus, ugyanezzel a gondolatmenettel belátható a fordított irányú egyenlőtlenség is: $(b, m) \le (a, m)$

A két egyenlőtlenségből együtt pedig $(a, m) = (b, m)$ valóban következik. □

3.2. Az Euler-féle $\phi$-függvény (1.5.2. Definíció)

1.5.2. Definíció:

Ha $n \ge 1$ egész, akkor az $1, 2, \dots, n$ számok között az $n$-hez relatív prímek számát $\phi(n)$-nel jelöljük. Az $n \mapsto \phi(n)$ függvényt Euler-féle $\phi$ függvénynek nevezzük. (A $\phi$ görög betű, kiolvasáskor „fí”-nek ejtjük.)

Példa a meghatározásra: $\phi(10)$ kiszámítása

$\phi(10)$ meghatározásához az $1, 2, \dots, 10$ számok között kell a 10-hez relatív prímeket megszámolnunk.

  • A páros számok ($2, 4, 6, 8, 10$) nyilván kiesnek.
  • A páratlanok közül is kiesik az $5$ (mert ezeknek van 1-nél nagyobb közös osztójuk a 10-zel).
  • A megmaradt $1, 3, 7$ és $9$ számok viszont már relatív prímek 10-hez.

Így $\phi(10) = 4$.

Speciális eset: Ha $n = p$ prímszám

Ha $n = p$ prímszám, akkor a definícióból rögtön adódik, hogy $\phi(p) = p - 1$.

Valóban: az $1, 2, \dots, p - 1$ számok mind relatív prímek $p$-hez (mert $p$-nek nincs 1-nél nagyobb és $p$-nél kisebb osztója), a $p$ viszont nyilván nem az.

Persze nagyobb, összetett $n$-ekre $\phi(n)$ kiszámítása a definíció alapján nagyon fáradságos volna. Egy későbbi tétel azonban ezt nagyban megkönnyíti: kiderül belőle, hogy $n$ prímtényezős felbontásából $\phi(n)$ könnyen megkapható.

3.3. Az Euler-függvény kiszámítása (1.5.3. Tétel)

1.5.3. Tétel:

Legyen az $n > 1$ egész szám kanonikus alakja $n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dots \cdot p_k^{\alpha_k}$. Ekkor:

$$\phi(n) = (p_1^{\alpha_1} - p_1^{\alpha_1-1}) \cdot (p_2^{\alpha_2} - p_2^{\alpha_2-1}) \cdot \dots \cdot (p_k^{\alpha_k} - p_k^{\alpha_k-1})$$

Részletes Bizonyítás:

Tegyük fel először, hogy $n$ prímtényezős felbontásában csak egyetlen prím van, vagyis $n = p^\alpha$ valamilyen $p$ prímre és $\alpha \ge 1$ egészre.

1. Ebben az esetben $(n, a) > 1$ akkor és csak akkor igaz, ha $p \mid a$. (Indoklás: hiszen $n$ prímtényezős felbontásában csak $p$ szerepel, így más közös prím nem lehet).

2. Ez tehát azt jelenti, hogy az $1, 2, \dots, n$ számok közül pontosan $\frac{n}{p} = p^{\alpha-1}$ darab nem relatív prím $n$-hez, ugyanis nyilván ennyi a $p$-vel oszthatók száma ebben a tartományban.

3. Így a definíció szerint a relatív prímek száma az összes szám és a nem relatív prímek számának különbsége: $\phi(n) = n - p^{\alpha-1} = p^\alpha - p^{\alpha-1}$

Következésképp a tétel igaz minden prímhatványra.

Az általános $n$-re vonatkozó állítás ebből könnyen következik a függvény multiplikativitásának felhasználásával (amelyet a jegyzet későbbi pontjai részleteznek).

Gyakorlati alkalmazás: $\phi(n)$ kiszámítása

Példa: Számítsuk ki $\phi(12)$ értékét!

  • 1. Kanonikus alak: $12 = 2^2 \cdot 3^1$
  • 2. Képlet alkalmazása:
  • $\phi(12) = (2^2 - 2^1) \cdot (3^1 - 3^0)$
  • $\phi(12) = (4 - 2) \cdot (3 - 1) = 2 \cdot 2 = 4$

Alternatív alak (Kiemeléssel):

$\phi(n) = n \cdot \prod_{p \mid n} (1 - \frac{1}{p})$

3.3. Az Euler-függvény kiszámítása (1.5.3. Tétel)

Interaktív kalkulátor részletes levezetéssel

3.4. A redukált maradékrendszer (1.5.5. Definíció)

1.5.5. Definíció:

Az $R = \{c_1, c_2, \dots, c_k\}$ számhalmaz redukált maradékrendszer modulo $m$, ha a következő feltételeknek eleget tesz:

  • (i) $(c_i, m) = 1$ minden $i = 1, 2, \dots, k$ esetén;
  • (ii) $c_i \not\equiv c_j \pmod m$ bármely $i \neq j, 1 \le i, j \le k$ esetén;
  • (iii) $k = \phi(m)$.

1.5.6. Állítás:

Legyen $R = \{c_1, c_2, \dots, c_k\}$ redukált maradékrendszer modulo $m$ és legyen $a$ tetszőleges egész, amelyre $(a, m) = 1$. Ekkor az $R' = \{a \cdot c_1, a \cdot c_2, \dots, a \cdot c_k\}$ halmaz szintén redukált maradékrendszer modulo $m$.

Részletes Bizonyítás:

Azt kell megmutatnunk, hogy az 1.5.5. Definíció feltételei teljesülnek $R'$-re, ha $R$-re igazak.

Az (i) feltétel: Ez a számelmélet alaptételéből következik, hiszen $a \cdot c_i$ és $m$ prímtényezős felbontásaiban nem lehet közös prím, ha sem $a$, sem $c_i$ prímfelbontásában nincs az $m$ felbontásában is szereplő prím.

A (ii) feltétel: Tegyük fel, hogy $a \cdot c_i \equiv a \cdot c_j \pmod m$ valamely $1 \le i, j \le k$ esetben.

Ekkor a kongruencia mindkét oldalát $a$-val osztva a $c_i \equiv c_j \pmod m$ kongruenciát kapjuk, hiszen $(a, m) = 1$ miatt (az 1.3.4. Tétel szerint) osztáskor a modulus nem változik.

Mivel $R$-re teljesül a (ii) feltétel, ez valóban csak az $i = j$ esetben fordulhat elő.

A (iii) feltétel: Végül $R$ és $R'$ elemszáma nyilván azonos, így a (iii) feltétel is teljesül $R'$-re.

A bizonyítás ezzel teljes. □

Redukált maradékrendszer meghatározása

Adja meg az m modulus értékét a kereséshez!

3.5. Az Euler-Fermat-tétel (1.5.7. Tétel)

1.5.7. Tétel (Euler-Fermat-tétel):

Ha az $a$ és $m \ge 2$ egészekre $(a, m) = 1$, akkor $a^{\phi(m)} \equiv 1 \pmod m$.

Részletes Bizonyítás:

1. Legyen $R = \{c_1, c_2, \dots, c_k\}$ egy tetszőleges redukált maradékrendszer modulo $m$.

2. Mivel a feltétel szerint $(a, m) = 1$, az 1.5.6. Állítás értelmében az $R' = \{a \cdot c_1, a \cdot c_2, \dots, a \cdot c_k\}$ halmaz szintén redukált maradékrendszer lesz modulo $m$.

3. Ebből következik, hogy $R$ és $R'$ elemei párba állíthatók úgy, hogy a párok tagjai kongruensek legyenek modulo $m$. (Ennek oka, hogy minden, az $m$-hez relatív prím $c$ maradékra $R$ és $R'$ is pontosan egy $m$-mel osztva $c$ maradékot adó számot tartalmaz).

4. Ebből (felhasználva a kongruenciák szorzására vonatkozó 1.3.3. Tétel (iii) tulajdonságát) következik, hogy $R$ és $R'$ elemeit összeszorozva egymással, modulo $m$ kongruens eredményeket kapunk:

$$c_1 \cdot c_2 \cdot \dots \cdot c_k \equiv (a \cdot c_1) \cdot (a \cdot c_2) \cdot \dots \cdot (a \cdot c_k) \pmod m$$

5. A jobb oldalt átrendezve (kiemelve az $a$ tényezőket) és felhasználva, hogy az RMR elemszáma $k = \phi(m)$:

$$c_1 \cdot c_2 \cdot \dots \cdot c_k \equiv a^{\phi(m)} \cdot c_1 \cdot c_2 \cdot \dots \cdot c_k \pmod m$$

6. Mivel minden $c_i$ relatív prím $m$-hez ($(c_i, m) = 1$), a számelmélet alaptételéből adódóan a szorzatuk is relatív prím lesz $m$-hez: $(c_1 \cdot c_2 \cdot \dots \cdot c_k, m) = 1$.

7. Ezért a fenti kongruencia mindkét oldalát elosztva a $(c_1 \cdot c_2 \cdot \dots \cdot c_k)$ szorzattal, a modulus nem változik (az egyszerűsítési szabály alapján), így éppen a tétel állítását kapjuk:

$$a^{\phi(m)} \equiv 1 \pmod m$$

Ezzel a tételt beláttuk. □

Alkalmazási feltétel

Soha ne felejtsd el ellenőrizni, hogy $(a, m) = 1$ teljesül-e! Ha a szám és a modulus nem relatív prímek, a tétel nem használható.

Speciális eset: Kis Fermat-tétel

Ha a modulus egy $p$ prím, akkor $\phi(p) = p-1$. Ekkor a képlet az $a^{p-1} \equiv 1 \pmod p$ alakot ölti.

3.6. A „Kis” Fermat-tétel (1.5.8. Következmény)

1.5.8. Következmény:

Ha $p$ prím és $a$ tetszőleges egész, akkor $a^p \equiv a \pmod p$.

Bizonyítás:

A tétel állítása magától értetődő, ha $p \mid a$: valóban, ekkor $p \mid a^p$ is nyilván igaz, így $a^p \equiv 0 \equiv a \pmod p$.

Ha viszont $p \nmid a$, akkor $(a, p) = 1$ is igaz (mert $p$ prím), így alkalmazhatjuk az 1.5.7. Euler-Fermat tételt $a$-ra és $p$-re.

Ez $\phi(p) = p - 1$ miatt a következőt állítja: $a^{p-1} \equiv 1 \pmod p$.

A kapott kongruencia mindkét oldalát $a$-val szorozva épp a tétel állítását kapjuk: $a^p \equiv a \pmod p$. □

Példafeladat: Maradékkeresés

Feladat:

Határozzuk meg a $3^{402}$ szám utolsó számjegyét tizes számrendszerben!

1. Matematikai modell felírása

Egy szám utolsó számjegye tizes számrendszerben a számnak a 10-zel vett osztási maradéka. A feladat tehát:
$3^{402} \equiv ? \pmod{10}$

2. Feltétel ellenőrzése

Alkalmazható-e az Euler-Fermat-tétel?
Mivel $a = 3$ és $m = 10$, a legnagyobb közös osztójuk $(3, 10) = 1$.
A feltétel teljesül, a tétel használható.

3. Euler-függvény kiszámítása

Számítsuk ki $\phi(10)$ értékét a kanonikus alak ($10 = 2^1 \cdot 5^1$) alapján:
$\phi(10) = (2^1 - 2^0) \cdot (5^1 - 5^0) = 1 \cdot 4 = 4$

4. A tétel alkalmazása és redukció

Az Euler-Fermat-tétel szerint: $3^4 \equiv 1 \pmod{10}$.
Osszuk el a kitevőt (402) a periódussal (4):
$402 = 100 \cdot \mathbf{4} + \mathbf{2}$ Most írjuk fel a hatványt ezen felbontás segítségével:

$3^{402} = (3^4)^{100} \cdot 3^2 \equiv 1^{100} \cdot 3^2 \pmod{10}$

5. Végeredmény

Mivel $1^{100} = 1$ és $3^2 = 9$:

$3^{402} \equiv 9 \pmod{10}$

Válasz: A szám utolsó számjegye a 9-es.

3. Tétel: Kongruenciarendszerek

Megoldás behelyettesítéssel (x ≡ a mod m)

I. Kongruencia (a1, m1)

x ≡ (mod )

II. Kongruencia (a2, m2)

x ≡ (mod )