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

Home > Numbers
Is this a Prime Number ? (Posted on 2023-05-23) Difficulty: 3 of 5
Is 987654 + 456789 a prime number?

Provide your answer with valid reasoning.

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 2
98765^4 mod 17 = 13

4^n goes in a length-4 cycle, mod 17, of 4, 16, 13, 1, ...

56789 is congruent to 1 mod 4, so 4 to that power is congruent to 4 mod 17

98765^4 + 4^56789 is therefore contruent to 13 + 4 mod 17, or 0 mod 17, and is thus divisible by 17, and is not prime.


A more direct approach (and what led me to the above), via computer:

a=sym(98765)^4;
b=sym(4)^56789;
n=a+b;
p=1;
for i=1:10000
  p=nextprime(p);
  if mod(n,p)==0
    disp(p)
    n=n/p;
  else
    p=p+1;
  end
end

finds that of the first 10,000 prime numbers, the given sum is divisible by:

    17
    41
    61
   521
   733
   769
 42169
 
This is a long way from completely factoring that 34191-digit number but it does show it's composite.


  Posted by Charlie on 2023-05-23 11:56:58
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 (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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