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).

[m_f_h]

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 ?

[akruppa]

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³ ≡ 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

[Citrix]

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)