"pseudoalgarvude" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

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' teoreemi rakendada mingi arvu p jaoks 10 erinva aluse a baasil, on eksimisvõimalus juba väiksem, kui 0,1%. Carmichaeli arvud- Carmichaeli arv on paaritu kordarv, mis rahuldab Fermat' teoreemi väidet iga aluse korral. Carmichaeli algarvud on Fermat' teoreemi suurimaks kirstunaelaks. Selleks aga, et Carmichaeli arvude probleemist kõrvale hiilida, rakendataksegi