Toplista
- betöltés...
Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!
2 kongruencia feladat
LosBlancos
kérdése
913
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!
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.
feladat, Matematika, számelmélet, kongruencia
feladat, Matematika, számelmélet, kongruencia
0
Felsőoktatás / Matematika
Válaszok
1
AlBundy
{ Polihisztor }
megoldása
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`.
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
- Még nem érkezett komment!