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

Home > Just Math
How fast can you solve it? (Posted on 2018-06-10) Difficulty: 2 of 5
32701 = 3 mod 2701

With neither calculator nor direct evaluation prove the above statement.

Generalize.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Some thoughts Comment 1 of 1

Note that 73=2*37-1, and 2701=37*73

Where p and (2p-1) are both prime, by Fermat:     
a^p mod p = a     
a^(2p-1) mod (2p-1) = a     
so a^(p(2p-1)) = a mod (p(2p-1))     

So the required answer is 3.    
     
Generalisation for prime p with p>a whether or not (2p-1) prime:     
p(2p-1)) = 2p^2-p     
a^(2p^2-p)=a mod p     
e.g.     
{a,p} = {11,17} = 11     
{a,p} = [23,37} = 23     
     
But not necessarily a^(2p^2-p)=a mod (2p^2-p)     
e.g.     
{a,p} = {11,17} = 11     
{a,p} = [23,37} = 23     
but      
{a,p} = [11,23} = 701, a prime.   



Edited on June 11, 2018, 11:30 am
  Posted by broll on 2018-06-11 02:01:06

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 (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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