Eulers phi function: n=57482=2*p1*p2 and phi (n) = 28000. Find the two different prime numbers p1 and p2.  

Expert Answers

An illustration of the letter 'A' in a speech bubbles

Using Euler's product formula we have that

`phi(n) = n prod_i (1-1/p_i)`

where the `p_i` are integers relatively prime to `n`.

Therefore since `n = 57482 = 2p_1p_2`

`phi(n) = 28000 = 57482(1-1/2)(1-1/(p_1))(1-1/(p_2)) `

`= 28741(1-1/(p_1))(1-1/(p_2))`

Rearranging, we get (the Diophantine equation)

1)  `(1-28000/28741)p_1p_2 - p_1 - p_2 +1 = 0`

We also have

2)  `p_1p_2 = n/2 = 28741`

Substituting into 1) implies

3)  `p_1 + p_2 = 742`

Since from 2)  `p_2 = 28741/p_1`    then

`p_1^2 - 742p_1 + 28741 = 0`

Solving this quadratic gives `p_1 = 701` and hence from 3) `p_2 = 41`.

``The other two prime factors of n are 41 and 701.

 

Approved by eNotes Editorial Team

We’ll help your grades soar

Start your 48-hour free trial and unlock all the summaries, Q&A, and analyses you need to get better grades now.

  • 30,000+ book summaries
  • 20% study tools discount
  • Ad-free content
  • PDF downloads
  • 300,000+ answers
  • 5-star customer support
Start your 48-Hour Free Trial