Kongruenciák

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

Megnézem, hogyan kell megoldani


2. 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


3. Mennyi $\varphi(7)$ ?

Megnézem, hogyan kell megoldani


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

Megnézem, hogyan kell megoldani


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

Megnézem, hogyan kell megoldani


6. Mi az utolsó két számjegye az alábbi számnak?

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

Megnézem, hogyan kell megoldani


7. 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


8. 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


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

a) \( 2x \equiv 14 \; \textrm{mod}\ 12 \)

b) \( 4x \equiv 36 \; \textrm{mod}\ 16\)

c) \( 14x \equiv 30 \; \textrm{mod}\ 18\)

d) \( 6x \equiv 10 \; \textrm{mod}\ 22\)

Megnézem, hogyan kell megoldani


10. Oldjuk meg az alábbi Diofantoszi egyenleteket.

a) \( 3x+4y=13 \)

b)  \( 13x+36y=56 \)

c)  \( 4x+6y=13 \)

Megnézem, hogyan kell megoldani


11. Oldjuk meg az alábbi kongruencia rendszereket

a)

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

\( x \equiv 9 \; \textrm{mod}\ 10 \)

b)

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

\( 5x \equiv 6 \; \textrm{mod}\ 7\)

Megnézem, hogyan kell megoldani


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

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

Megnézem, hogyan kell megoldani


14.

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

\( 1025^{1005} \)

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

\( 138^{139} \)

Megnézem, hogyan kell megoldani


15. 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


16. 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


17. 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


18.

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


19. 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