With neither calculator nor direct evaluation prove the above statement.

Generalize.

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