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

Home > Just Math
Not a Prime (Posted on 2012-12-20) Difficulty: 3 of 5
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.)
Solution 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information