According to the Fermat primality test:
Given an integer n, choose some integer a coprime to n and calculate a^(n - 1) modulo n. If the result is different from 1, then n is composite. If it is 1, then n may or may not be prime.
Using the extra precision of UBASIC we find:
5^100 + 5^75 + 5^50 + 5^25 + 1 = 7888609052210118080587065254524747981434984467341564893722534179687501,
When 12345 is raised to this number minus 1, mod this number, the modular value is 6868103652859355169395605010503922838541064350664959700576651963484114,
which is not 1.
So the number is not prime.
10 N=7888609052210118080587065254524747981434984467341564893722534179687501
20 for Dvsr=12345 to 99999
30 if N @ Dvsr = 0 then print Dvsr:cancel for:goto *Found
40 P=modpow(Dvsr,N-1,N)
50 if P<>1 then print "not prime":print Dvsr:print P:cancel for:goto *Nprime
60 next
65 print "couldn't prove"
70 *Found
80 *Nprime
90 end
The modpow function in UBASIC raises the first parameter to the second parameter power mod the third parameter. In the case of Dvsr = 12345, it indeed found 6868103652859355169395605010503922838541064350664959700576651963484114.
|
Posted by Charlie
on 2012-12-20 21:10:39 |