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

## 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

Already a member? Log in here.

Are you a teacher? Sign up now