Jump to navigation

Belépés
  • Elfelejtettem a jelszavam
Regisztráció
 
  • Hogyan működik a mateking?
  • Mire jó a matek?
  • Matek érettségi
  • Képletgyűjtemény
  • Feladatgyűjtemény
  • Rólunk
  • Matek 5. osztály próbaüzem
  • Matek 6. osztály próbaüzem
  • Matek 7. osztály próbaüzem
  • Matek 8. osztály próbaüzem
  • Matek 9. osztály
  • Matek 10. osztály
  • Matek 11. osztály
  • Matek 12. osztály
  • Középiskolai matek (teljes)
  • Középszintű matek érettségi
  • Emelt szintű matek érettségi
  • Egyetemi matek alapozó
Összes egyetemi tantárgy
Legnépszerűbb tantárgyak:
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Valószínűségszámítás
  • Lineáris algebra
  • Diszkrét matematika
  • Statisztika

mateking

Login
 

Diszkrét matematika

Kategóriák
  • Kombinatorika
  • Halmazok, rendezett párok, leképezések
  • Matematikai logika, ítéletkalkulus
  • Gráfelméleti alapok
  • Gráfok izomorfiája és síkbarajzolhatósága
  • Gráfok bejárása és gráfalgoritmusok
  • Kromatikus szám, klikk, perfekt gráfok
  • Gráfparaméterek, párosítások
  • Hálózatok
  • Irányított gráfok, gráfalgoritmusok irányított gráfokban
  • Menger tételei, többszörös összefüggőség
  • Páros gráfok, párosítások
  • Teljes indukció
  • Oszthatóság
  • Euklideszi algoritmus & Diofantoszi egyenletek
  • Kongruenciák
  • Mátrixok
  • Lineáris egyenletrendszerek
  • Determinánsok
  • Komplex számok
  • Polinomok
  • Interpolációs polinomok
  • Csoportok, gyűrűk, testek

Kongruenciák

  • Epizódok
  • Feladatok
  • Képletek
01
 
Mi az a kongruencia?
02
 
Műveletek kongruenciákban
03
 
Maradékosztály, redukált maradékosztály
04
 
Az Euler-féle fí függvény
05
 
Az Euler-Fermat tétel
06
 
A Kis Fermat-tétel és az Euler-Fermat tétel
07
 
Lineáris kongruenciák megoldása
08
 
Lineáris kongruenciák megoldása 2.
09
 
Lineáris kongruenciák megoldása 3.
10
 
Diofantoszi egyenletek megoldása
11
 
Szimultán kongruencia rendszerek
12
 
Kínai maradéktétel
13
 
Az RSA kódolás
14
 
FELADAT | Kongruenciák
15
 
FELADAT | Kongruenciák
16
 
FELADAT | Kongruenciák
17
 
FELADAT | Kongruenciák
18
 
FELADAT | Kongruenciák
19
 
FELADAT | Kongruenciák

Kongruencia

Ha $a$ és $b$ ugyanazt a maradékot adja $m$-mel osztva, akkor azt mondjuk, hogy $a$ és $b$ kongruensek modulo $m$, és ezt a tényt így jelöljük:

\( a \equiv b \; \textrm{mod}\ m \)

Megnézem a kapcsolódó epizódot

Kongruenciák tulajdonságai

Reflexív:

\( a \equiv a \; \textrm{mod}\ m \)

Szimmetrikus:

\( a \equiv b \; \textrm{mod}\ m \Rightarrow b \equiv a \; \textrm{mod}\ m\)

Tranzitív:

$a \equiv b \; \textrm{mod}\ m$ és $b \equiv c \; \textrm{mod}\ m \Rightarrow a \equiv c \; \textrm{mod}\ m $

Összefüggés összeadásra:

$ a \equiv b \; \textrm{mod}\ m$ és $c \equiv d \; \textrm{mod}\ m \Rightarrow a+c \equiv b+d \; \textrm{mod}\ m$

Összefüggés szorzásra:

$ a \equiv b \; \textrm{mod}\ m$ és $c \equiv d \; \textrm{mod}\ m \Rightarrow a\cdot c \equiv b\cdot d \; \textrm{mod}\ m$

Megnézem a kapcsolódó epizódot

Kongruencia vizsgálata

Legyenek $a$ és $b$ egész számok és $m$ pozitív egész szám.

Ekkor

$a \equiv b \; \textrm{mod}\ m$, ha $ m \mid a-b$

Megnézem a kapcsolódó epizódot

Műveletek kongruenciákban

\( a \equiv b \; \textrm{mod}\ m \Rightarrow a\cdot c \equiv b\cdot c \; \textrm{mod}\ m \)

\( a\cdot c \equiv b\cdot c \; \textrm{mod}\ m \Rightarrow a \equiv b \; \textrm{mod}\ m \quad (m,c)=1\)

Megnézem a kapcsolódó epizódot

Maradékosztály

Egy adott $m$ modulus esetén az $a$-val kongruens elemek halmazát az $a$ által reprezentált maradékosztálynak nevezzük.

Megnézem a kapcsolódó epizódot

Redukált maradékosztály

Egy mod $m$ modulus esetén az $m$-hez relatív prím elemekből álló maradékosztályokat redukált maradékosztálynak nevezzük.

A redukált maradékosztályok számát a $\varphi(m)$ számelméleti függvény írja le.

Megnézem a kapcsolódó epizódot

Euler-féle fí függvény

Az euler féle $ \varphi$ függvény azt adja meg, hogy hány $m$-nél nem nagyobb, $m$-hez relatív prím pozitív szám létezik.

Ha $p$ prím, akkor

\( \varphi (p) = p-1 \)

\( \varphi(p^{\alpha} = p^{\alpha} - p^{\alpha -1 } \)

És ha

\( m = p_1^{\alpha_1} \cdot  p_2^{\alpha_2} \cdot \dots \cdot  p_n^{\alpha_n} \)

akkor

\( \varphi(m) = \left (  p_1^{\alpha_1} -  p_1^{\alpha_1 - 1} \right) \cdot \dots \cdot \left (  p_n^{\alpha_n} -  p_n^{\alpha_n - 1} \right) \)

Továbbá

\( \varphi(ab) = \varphi(a) \cdot \varphi(b) \)

Megnézem a kapcsolódó epizódot

Euler-Fermat tétel

$ a^{ \varphi(m)} \equiv 1 \; \textrm{mod}\ m $ ha $(a,m)=1$

Megnézem a kapcsolódó epizódot

Kis Fermat tétel

$ a^p \equiv a \; \textrm{mod}\ p$ ha $p$ prím

Megnézem a kapcsolódó epizódot

Lineáris kongruenciák

A lineáris kongruenciák így néznek ki:

\( ax \equiv b \; \textrm{mod}\ m \)

És érdemes megjegyezni, hogy csak akkor oldhatók meg, ha $(a,m) \mid b$.

Megnézem a kapcsolódó epizódot

Lineáris kongruenciák megoldása

A lineáris kongruenciák így néznek ki:

\( ax \equiv b \; \textrm{mod}\ m \)

Megoldás csak akkor létezik, ha $(a,m) \mid b$.

A megoldás menete a következő:

1. lépés: Redukálunk

\( a_1 x \equiv b_1 \; \textrm{mod}\ m \)

2. lépés: Leosztunk $a_1$-gyel, de $b_1$-et lélekben fel kell erre készíteni

A megoldások száma: $(a,m)$

Megnézem a kapcsolódó epizódot

RSA kódolás

Az RSA lényege, hogy a titkosítás kulcsa nyilvános, vagyis azt bárki ismerheti. Csak a dekódolás kulcsa az, ami titkos.

Az alapötlete a következő:

Veszünk két jó nagy prímet, $p$-t és $q$-t amit csak mi ismerünk, ezek titkosak.

Elkészítjük az $N=p \cdot q$ számot és $\varphi(N)$-et, amit csak mi ismerünk.

Ha $p$ és $q$ többszázjegyű prímek, akkor $N$ prímfelbontása a jelenlegi számítógépekkel több ezer évig tartana, és így $\varphi(N)$ kiszámolása is lehetetlen.

Végül már csak egy dolog kell, egy $e$ kitevő, amire teljesül, hogy $ \left( e, \varphi(N) \right) = 1 $

Ezt követően jön a titkosítás.

A visszafejtéshez pedig az Euler-Fermat tétel kell, aminek segítségével megalkotjuk a $d$ megfejtő kulcsot.

Megnézem a kapcsolódó epizódot

1.

a) Bizonyítsuk be, hogy $a \equiv b \; \textrm{mod}\ m \Rightarrow a\cdot c \equiv b \cdot c \; \textrm{mod}\ m $

b) Bizonyítsuk be, hogy $a\cdot c \equiv b\cdot c \; \textrm{mod}\ m \Rightarrow a \equiv b \; \textrm{mod}\ m $

Megnézem, hogyan kell megoldani

2.

Mennyi $\varphi(7)$ ?

Megnézem, hogyan kell megoldani

3.

Mennyi $\varphi(12)$, $\varphi(16)$ és $\varphi(100)$ ?

Megnézem, hogyan kell megoldani

4.

Bizonyítsuk be az Euler-Fermat tételt.

Megnézem, hogyan kell megoldani

5.

a) Mi az utolsó két számjegye a $1789^{2046}$-nak?

b) Mi az utolsó két számjegye az alábbi számnak?

\( 39^{49^{59}} \)

Megnézem, hogyan kell megoldani

6.

Keressük azokat az $x$ egész számokat, amikre

a) \( 24x \equiv 13 \; \textrm{mod}\ 7\)

b) \( 13x \equiv 11 \; \textrm{mod}\ 120 \)

c) \( 13x \equiv 611 \; \textrm{mod}\ 120 \)

Megnézem, hogyan kell megoldani

7.

Keressük azokat az $x$ egész számokat, amikre

a) \( 59x \equiv 11 \; \textrm{mod}\ 120\)

b) \( 23x \equiv 63\; \textrm{mod}\ 43\)

Megnézem, hogyan kell megoldani

8.

Oldjuk meg az alábbi kongruencia rendszert

\( x \equiv 2 \; \textrm{mod}\ 3\)

\( x \equiv 3 \; \textrm{mod}\ 5\)

\( x \equiv 4 \; \textrm{mod}\ 7\)

Megnézem, hogyan kell megoldani

9.

a) Milyen maradékot ad 66-tal osztva ez a szám?

\( 66^{63^{61}} \)

b) Milyen maradékot ad 1023-mal osztva ez a szám?

\( 1025^{1005} \)

c) Milyen maradékot ad 65-tel osztva ez a szám?

\( 138^{139} \)

Megnézem, hogyan kell megoldani

10.

Mi lesz az utolsó két számjegye ennek az alábbi számoknak?

a) \( 303^{404} \)

b) \( 33^{21^{34}} \)

Megnézem, hogyan kell megoldani

11.

Mi lesz az utolsó két számjegye ennek az alábbi számoknak?

a) \( 159^{161} \)

b) \( 49^{49^{50}} \)

Megnézem, hogyan kell megoldani

12.

Oldjuk meg az alábbi lineáris kongruenciákat.

a) \( 8x \equiv 30 \; \textrm{mod}\ 28\)

b) \( 2x \equiv 7\; \textrm{mod}\ 33\)

c) \( 47x \equiv 1\; \textrm{mod}\ 53\)

d) \( 9x \equiv 1\; \textrm{mod}\ 88\)

e) \( 8x \equiv 29\; \textrm{mod}\ 27\)

f) \( 32x \equiv 7\; \textrm{mod}\ 47\)

Megnézem, hogyan kell megoldani

13.

a) Egy $n$ egész szám 115-szöröse 110-zel nagyobb maradékot ad 344-gyel osztva, mint maga az $n$ szám. Milyen maradékot adhat $n$ 344-gyel osztva?

b) Az $n$ pozitív egész számra $43n-1$ utolsó két számjegye megegyezik $2n+2$ utolsó két számjegyével. Mi ez a két számjegy?

Megnézem, hogyan kell megoldani

14.

Mely egész számokra teljesül, hogy 7-tel osztva 2, 9-cel osztva 3 maradékot adnak?

Megnézem, hogyan kell megoldani

A témakör tartalma


Mi az a kongruencia?

Műveletek kongruenciákban

Maradékosztály, redukált maradékosztály

Az Euler-féle fí függvény

Az Euler-Fermat tétel

A Kis Fermat-tétel és az Euler-Fermat tétel

Lineáris kongruenciák megoldása

Lineáris kongruenciák megoldása 2.

Lineáris kongruenciák megoldása 3.

Diofantoszi egyenletek megoldása

Szimultán kongruencia rendszerek

Az RSA kódolás

FELADAT | Kongruenciák

FELADAT | Kongruenciák

FELADAT | Kongruenciák

FELADAT | Kongruenciák

FELADAT | Kongruenciák

FELADAT | Kongruenciák

Kínai maradéktétel

Kapcsolatfelvétel
  • Segítségnyújtás
  • Hibabejelentés
  • Kapcsolatfelvétel
  • Mateking torrent bejelentés
Rólunk
  • A projektről
  • Médiamegjelenések
  • Legyen élmény a matek
  • Mire jó a matek?
Tartalomjegyzék
  • Középiskolai matek
  • Analízis 1
  • Analízis 2
  • Analízis 3
  • Lineáris algebra
  • Valószínűségszámítás
  • Diszkrét matematika
  • Statisztika
  • További tantárgyak
  • Egyetemi tematikák
  • Matek érettségi
GYIK Általános szerződési feltételek Adatkezelési tájékoztató Felhasználás oktatási célra

Cookie-használat módosítása

© Minden jog fenntartva!

Az oldalon található tartalmak részének vagy egészének másolása, elektronikus úton történő tárolása vagy továbbítása, harmadik fél számára nyújtott oktatási célra való hasznosítása kizárólag az üzemeltető írásos engedélyével történhet. Ennek hiányában a felsorolt tevékenységek űzése büntetést von maga után!

barion
macroweb
  • Tantárgyaim