20070315, 23:03  #1 
5,807 Posts 
application of euler's phi function
Question using euler's phi function
Let p be an odd prime number, and suppose that p  1 is not divisible by 3. Prove that, for every integer a, there is an integer x, such that x^3 is defined as a (mod p). 
20070426, 20:07  #2 
Feb 2007
660_{8} Posts 

20070427, 08:03  #3 
"Nancy"
Aug 2002
Alexandria
4643_{8} Posts 
Puzzles, or maybe homework? Sounds like a typical question on RSA from an Introduction to Cryptography course.
So what you want to prove, I guess, is that for every a (mod p), x^{3} ≡ a (mod p) has a unique solution, if p ≡ 2 (mod 3). One way of going about this proof is using the fact that (Z/pZ)* is a cyclic group, using the isomorphy to the group {0, ..., p1} with addition, and showing that dividing by three always has a unique solution there (use the extended GCD). Hint: Why is taking cube roots in (Z/pZ)* equivalent to dividing by three in {0, ..., p1} with addition? I.e., what isomorphic map are we using? If you never heard any group theory, none of the above might make any sense. But if you're studying RSA, you probably did. Alex Last fiddled with by akruppa on 20070427 at 10:05 Reason: Missing ()* 
20070427, 11:50  #4 
Jun 2003
3·5·107 Posts 
There is an easier approach.
X^3=a (mod p) Then you calculate x^3*n=a^n (mod p) and choose n such that 3*n% (p1)==1 so you get x=a^n (mod p). Thus for any given a you can solve for x. I leave it up to you to show that for all primes such that p%3==2, there exists an n. (I suspect this to be an homework problem) 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 7: idempotents and Euler's function  Nick  Number Theory Discussion Group  17  20161201 14:27 
Srsieve Application failed  PawnProver44  Information & Answers  12  20160311 00:43 
lasievee application  pinhodecarlos  NFS@Home  2  20130519 20:23 
Ports of the application  nohero  Twin Prime Search  9  20070617 10:12 
euler's totient function  toilet  Math  1  20070429 13:49 