"liitmismeetodiga" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

meelepärane lõppjagatis. *Selleks, et leida aga avaldise 1/b väärtust, peame jällegi rakendama Eukleidese algoritmi laiendatud versiooni kujul gcd(x,p). *Jagamistehte olemasolu võimaldab meil teatud juhtudel lahendada modulaararitmeetilisi lineaarseid võrrandeid ning isegi modulaararitmeetilisi võrrandsüsteeme. *Alternatiivselt on moodularitmeetilisi võrrandeid võimalik lahendada mooduli kordsete liitmismeetodiga ning võrrandsüsteeme hiina jäägiteoreemi abil. *Lisaks 12-tunnisele kellale on headeks moodularitmeetika näideteks veel nö. ,,nädalapäevade aritmeetika" (mod 7) ning Boole'i loogikaalgebra (mod 2). [30]. Algarvulisuse Fermat` test. Miller-Rabini test. *Fermat test: Fermat' teoreemist tulenevalt on teada, et kui p on algarv ja 1 < a < p, siis ap - 1 1 (mod p) ehk ap a (mod p). *Seega, et Fermat' testi abil kontrollida, kas naturaalarv n on kordarv või algarv: a)