"kürpteerimine" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

samuti võimalik leida Eukleidese algoritmi abil. Äärmiselt kasulik on siin omadus a*b = lcm(a,b) * gcd(a,b) [25].Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud. *Fermat' väike teoreem- teoreem ütleb, et kui p on algarv, siis iga täisarvu a korral, mis ei jagu p-ga, kehtib seos p|ap-1 ­ 1 , samaväärne esitus on p|ap ­ a. *Fermat' teoreemi avastas prantsuse matemaatik Pierre de Fermat 17. sajandil. *Teoreem on väga tähtis ka tänapäevases maailmas, kuna kürpteerimine on sageli seotud algarvudega ning just Fermat' teoreem võimaldab välja selgitada, kas arv x on algarv. *Mõningatel juhtudel võib aga Fermat' teoreem anda positiivse tulemuse ka siis, kui p ei ole tegelikult algarv: Pseudoalgarvud- pseudoalgarvud on sellised kordarvud, mis teatud aluse a korral võivad Fermat' teoreemi järgi ,,käituda" kui algarvud. Pseudoalgarvude probleemi võimaldab aga lahendada Fermat' teoreemi rakendamine mitmel erineval alusel a. Kui näiteks Fermat'