Homework Help

Find the form of all integers `n` satisfying `phi(n)=10`, where `phi` is Euler's...

user profile pic

svjr | Student, Undergraduate | (Level 2) Honors

Posted October 12, 2011 at 3:37 AM via web

dislike 1 like

Find the form of all integers `n` satisfying `phi(n)=10`, where `phi` is Euler's `phi` function. What is the smallest integer for which this is true?

 

2 Answers | Add Yours

user profile pic

mathsworkmusic | (Level 1) Educator

Posted April 28, 2013 at 8:21 PM (Answer #1)

dislike 1 like

The definition of Euler's `phi` function is that `phi(n)` equals the number of positive integers less than or equal to `n` that are coprime, or relatively prime to `n`. Coprimes have a greatest common denominator of 1.

Euler's product formula gives that `n` satisfies

`phi(n) = n prod_(p_n)(1-1/p)`

so we have that, since `phi(n) = 10`,

`n prod_(p_n)(1-1/p) = 10`

where the product is taken over prime factors of `n`.

The smallest `n` that gives `phi(n) = 10` is  `n=11`. This can be seen using the product formula:

`phi(11) = 11 prod_(p_n)(1-1/p) = 11 (1-1/11) = 11(10/11) = 10`

Since 11 is prime, 11 is the only prime factor of 11. The 10 coprimes of 11 are

2,3,4,5,6,7,8,9,10

The smallest integer satisfying phi(n) = 10 is n = 11

 

user profile pic

mathsworkmusic | (Level 1) Educator

Posted April 28, 2013 at 8:26 PM (Answer #2)

dislike 0 like

1 is also coprime to 11...

 

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes