All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Not a Prime (Posted on 2012-12-20)
Prove that 5100+575+550+525+1 is not a prime number.

 No Solution Yet Submitted by Danish Ahmed Khan Rating: 3.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 a proof | Comment 1 of 6

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

 Search: Search body:
Forums (0)