mersenneforum.org > Math application of euler's phi function
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

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

Feb 2007

6608 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 46438 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 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% (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 00:51.

Mon Jan 30 00:51:26 UTC 2023 up 164 days, 22:20, 0 users, load averages: 1.44, 1.12, 1.09

Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔