mersenneforum.org > Math application of euler's phi function
 Register FAQ Search Today's Posts Mark Forums Read

 2007-03-15, 23:03 #1 TalX   22×34×29 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).
2007-04-26, 20:07   #2
m_f_h

Feb 2007

24×33 Posts

Quote:
 Originally Posted by TalX ..., such that x^3 is defined as a (mod p).
"defined as" = "equal to" ? should this go into the "puzzles" section ?

 2007-04-27, 08:03 #3 akruppa     "Nancy" Aug 2002 Alexandria 2,467 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), x3 ≡ 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, ..., p-1} 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, ..., p-1} 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 2007-04-27 at 10:05 Reason: Missing ()*
 2007-04-27, 11:50 #4 Citrix     Jun 2003 22×397 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% (p-1)==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)

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 17 2016-12-01 14:27 PawnProver44 Information & Answers 12 2016-03-11 00:43 pinhodecarlos NFS@Home 2 2013-05-19 20:23 nohero Twin Prime Search 9 2007-06-17 10:12 toilet Math 1 2007-04-29 13:49

All times are UTC. The time now is 09:13.

Fri Aug 12 09:13:35 UTC 2022 up 36 days, 4 hrs, 2 users, load averages: 1.36, 1.22, 1.25