20.500.12556/RUL-188668 Kvadratne kongruence in kvadratni ostanki magistrsko delo Quadratic congruences and quadratic residues Kvadratni ostanek po modulu m je celo število a, za katero je kvadratna kongruenca x^2 ≡ a (mod m) rešljiva. Preprosto vprašanje, katera števila so kvadratni ostanki po izbranem modulu, vodi do obsežne teorije s širokim področjem uporabe. V magistrskem delu obravnavamo kvadratne kongruence in kvadratne ostanke, posebna pozornost pa je namenjena Zakonu kvadratne recipročnosti. Ta nam podaja zanimivo medsebojno povezavo med kvadratnimi ostanki. Predstavljeni so Legendrov simbol, Eulerjev kriterij in Gaussova lema, ki omogočajo določanje kvadratnega značaja števil. Recipročnost dokažemo z Zolotarevovo lemo, ki kvadratne ostanke poveže s permutacijami. Z Jacobijevim simbolom nato obravnavo razširimo s praštevilskih na sestavljene module. Predstavljeni so tudi pogoji za rešljivost kvadratnih kongruenc in število njihovih rešitev glede na različne oblike modula. V zadnjem delu so predstavljene nekatere uporabne aplikacije, vključno s testi praštevilskosti, kot sta Solovay-Strassenov verjetnostni test in Pépinov test, ter kriptografska aplikacija Blumovega protokola za pošten met kovanca na daljavo. Uporabnost predstavljenih rezultatov je prikazana tudi na izbranih problemskih nalogah z mednarodnih tekmovanj. A quadratic residue modulo m is an integer a for which the quadratic congruence x^2 ≡ a (mod m) has a solution. The seemingly simple question of which integers are quadratic residues modulo a given integer leads to an extensive theory and a broad range of applications. This master's thesis focuses on quadratic congruences and quadratic residues, with particular emphasis on the Law of Quadratic Reciprocity, which reveals an important relationship between quadratic residues. The Legendre symbol, Euler's criterion and Gauss's lemma are introduced as tools to determine the quadratic nature of integers modulo an odd prime. Quadratic reciprocity is proved using Zolotarev's lemma, which establishes a connection between quadratic residues and permutations. The use of the Jacobi symbol then extends our discussion from prime to composite moduli. Conditions for solvability of quadratic congruences and the number of their solutions for different types of moduli are also presented. The final part discusses several applications, including primality tests such as the Solovay-Strassen probabilistic primality test and Pépin's test as well as Blum's cryptographic protocol for coin flipping by telephone. The usefulness of the presented results is further illustrated through selected problems from international mathematical competitions. matematika teorija števil kvadratna kongruenca kvadratni ostanek Legendrov simbol Jacobijev simbol Zakon kvadratne recipročnosti quadratic congruence quadratic residue Legendre symbol Jacobi symbol Law of quadratic reciprocity true false false L. Žinko Slovenski jezik Angleški jezik Magistrsko delo/naloga 2026-09-25 08:31:39 2026-09-25 08:31:44 2026-09-29 13:03:55 0000-00-00 00:00:00 2026 0 Ljubljana 0 Ljubljana 72 str. 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 511(043.2) 211881 292915971 55212.pdf 55212.pdf 1 90FF4A5FEC6921F9575CF3B15B8626AA 7d0be3e13c0fc862e44133e16756b36098aaf0d7671df9d69c34f00ed7d979d2 b30c9700-b8aa-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=248971 Pedagoška fakulteta 0 0 0