Matematické Fórum

denvan · 12. 05. 2021 22:33

Ahoj, najdu tady někoho, kdo by mi pomohl s řešením těchto příkladů na kvadratické kongruence?
Něco málo k některým z nich mám, ale potřebovala bych mít jistotu, jak se to přesně počítá a co je dobře, aby mi to něco dalo. Bohužel ke kvadratickým kongruencím tolik konkrétních a názorných příkladů není, abych to díky tomu dokázala vypočítat. Finanční odměna za vaše výpočty je jistá. Děkuji!

Řešte následující kongruence 𝑥^2≡𝑎 (mod 𝑝) a spočítejte příslušné Legendrovy symboly (𝑎/𝑝):
𝑥^2≡2 (mod 13)
𝑥^2≡19 (mod 31)
𝑥^2≡523 (mod 269)
Řešte následující kongruence 𝑥^2≡𝑎 (mod 𝑛) a spočítejte příslušné Jacobiho symboly (𝑎/𝑛):
𝑥^2≡16 (mod 30)
𝑥^2≡29 (mod 33)
𝑥^2≡17 (mod 2021)

denvan · 12. 05. 2021 22:43

O prvním a třetím příkladu jsem přes Legendrovy symboly zjistila (snad správně), že nemají řešení, takže jde spíše o ten zbytek.

Richard Tuček

Kongruenční rovnice x^2=2 (mod 13) nemá řešení
0^2=0, 1^2=1, 2^2=4, 3^2=9, 4^2=16~3, 5^2=25~12, 6^2=36~10, atd.

Výše uvedená čísla jsou kvadratické zbytky modulo 13
číslo 2 je kvadratický nezbytek

O kongruencích je též na mém webu: www.tucekweb.info

Nevím, co to je ten Jacobiho či Legendrův symbol.

Richard Tuček

Kongruenční rovnici x^2=19 (mod 31) lze vyřešit zkusmo:

x^2=19 ~ 81 (mod 31)
řešení: x1=9, x2=-9~22 (mod 31)

číslo 19 je kvadratický zbytek modulo 31

Richard Tuček

Kongruenční rovnice x^2=16 (mod 30) má dokonce 4 řešení (modul není prvočíselný)

x1=4, x2=-4~26, x3=16 (16^2=256~16 (mod 30)), x4=14 (14^2=196~16)

číslo 29 je asi kvadratický nezbytek mod 33

PS
Okruh celých čísel rozfaktorizovaný podle kongruence modulo p je těleso právě tehdy, když p je prvočíslo. Proto hrají kongruence podle prvočíselného modulu významnou roli.

vanok · 13. 05. 2021 15:09 — Editoval vanok (13. 05. 2021 15:09)

Ahoj ↑ denvan:,

Najprv mala otazka. Tvoje cvicenia su take, co mas riesit vdaka prednaske co si uz mala?

Napr. na niektore otazky odpovies hravo, ak pouzijes tuto vetu z prednasok:
Cislo je kvadraticke resdum modulo p len a len ak [mathjax]a^{\frac {p-1}2 } \equiv 1
[/mathjax] ( mod p)

Autor skryl část textu. Zobrazit/skrýt!

No mozno studujes cez video konferencie a vtedy je to trocha tazsie studovat….
Atd….

Na vsetki tvoje otazky sa normalne mozu pouzit vety z prednasok!

denvan · 18. 05. 2021 09:41

↑ Richard Tuček:
Děkuji za vaše odpovědi, už jsem se do toho konečně více dostala. Kvadratické zbytky a nezbytky mi problém nedělaly, úplně jsem ale nevěděla, jak toho využít např. u těch těžších rovnic (poslední tři úlohy), které jsou modulo složené číslo.
Už jsem to snad ale vše rozlouskla, dá se to řešit pomocí různých algoritmů.

denvan · 18. 05. 2021 09:43

↑ vanok:
Na toto téma jsme měli jednu online přednášku, kde se toho moc probrat nestihlo, spíše jen ty KZ, KN a symboly. Proto hledám hlavně sama a snažím se to co nejvíce procvičit. Už by to ale snad mělo být v pořádku.
Děkuji.

Matematické Fórum

#1 12. 05. 2021 22:33

kvadratické kongrunce, Legendrovy a Jacobiho symboly

#2 12. 05. 2021 22:43

Re: kvadratické kongrunce, Legendrovy a Jacobiho symboly

#3 13. 05. 2021 13:13 — Editoval Richard Tuček (13. 05. 2021 13:16)

Re: kvadratické kongrunce, Legendrovy a Jacobiho symboly

#4 13. 05. 2021 13:21 — Editoval Richard Tuček (13. 05. 2021 13:23)

Re: kvadratické kongrunce, Legendrovy a Jacobiho symboly

#5 13. 05. 2021 13:35 — Editoval Richard Tuček (13. 05. 2021 14:41)

Re: kvadratické kongrunce, Legendrovy a Jacobiho symboly

#6 13. 05. 2021 15:09 — Editoval vanok (13. 05. 2021 15:09)

Re: kvadratické kongrunce, Legendrovy a Jacobiho symboly

#7 18. 05. 2021 09:41

Re: kvadratické kongrunce, Legendrovy a Jacobiho symboly

#8 18. 05. 2021 09:43

Re: kvadratické kongrunce, Legendrovy a Jacobiho symboly

Zápatí