Keresés

Keresendő kifejezés:

Toplista

Toplista
  • betöltés...

Segítség!

Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!

2 kongruencia feladat

444
1. Adjon meg olyan legalább hétjegyű pozitív egész x-t melyre
x ≡ 24 mod(78) és x ≡ 38 mod(97)

2. Adjon meg olyan 10000-nél nagyobb pozitív egész számot, melynek
11-dik hatványa 4 maradékot ad 91-gyel osztva!

Köszönöm előre is!
Jelenleg 1 felhasználó nézi ezt a kérdést.
Matematika, kongruencia, feladat, számelmélet
0
Felsőoktatás / Matematika

Válaszok

1
1.)
A második kongruencia szerint `x=97k+38`. Helyettesítsük ezt be az első kongruenciába, és oldjuk meg `k`-ra:
`97k+38 -= 24` (mod 78)
`97k -= -14` (mod 78)
`97k -= 64` (mod 78)
`19k -= 64` (mod 78)
`37*19k -= 37*64` (mod 78)
`k -= 28` (mod 78)

Az utolsó lépésben azért szoroztam be 37-tel mert ez a 19 multiplikatív inverze (`19*37=703-=1`). Ezt például a kiterjesztett euklideszi algoritmussal lehet megtalálni: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers

Tehát `k=78l+28`. Innen pedig `x=97*(78l+28)+38=7566l+2754`. Például `l=1000` esetén `x=7568754` hétjegyű.

2.)
Erre most csak "csúnya", próbálkozós megoldásom van. `91=7*13`, tehát a feladat az alábbi kongruenciarendszer megoldása:
`x^11 -= 4` (mod 7)
`x^11 -= 4` (mod 13)

Egy-egy különböző megoldás gyorsan található az egyes kongruenciákra:
`2^11 -= 4` (mod 7)
`10^11 -= 4` (mod 13)

Nekünk természetesen nem különböző megoldások kellenek, viszont ebből annyit már tudunk, hogy a keresett `x` szám 7-tel osztva 2 maradékot ad, 13-mal osztva pedig 10-et. Az első ilyen szám a 23, és valóban fennáll, hogy:
`23^11 -= 4` (mod 91)

Tehát bármilyen `91k+23` alakú szám kielégíti a kongruenciát, például `k=1000` esetén `x=91023`.
2