Question

Find the following Euler Totients using Euler’s Theorem, as explained on p.409 of the text (10 points each): a.ϕ(13) b.ϕ(81) c.ϕ(100) d.ϕ(102)

Answer 1

(a) $\varphi(13)=12$ since 13 is prime.

(b) $81=3^4$, and there are 81/3 = 27 multiples of 3 between 1 and 81, which leaves 81 - 27 = 54 numbers between 1 and 81 that are coprime to 81, so $\varphi(81)=54$.

(c) $100=2^2\cdot5^2$; there are 50 multiples of 2, and 20 multiples of 5, between 1 and 100; 10 of these are counted twice (the multiples of 2*5=10), so a total of 50 + 20 - 10 = 60 distinct numbers not coprime to 100, leaving us with $\varphi(100)=100-60=40$.

(d) $102=2\cdot3\cdot17$; there are 51 multiples of 2, 34 multiples of 3, and 6 multiples of 17, between 1 and 102. Among these, we double-count 17 multiples of 2*3=6, 3 multiples of 2*17=34, and 2 multiples of 3*17=51; we also triple-count 1 number, 2*3*17=102. There are then 51 + 34 + 6 - (17 + 3 + 2) + 1 = 70 numbers between 1 and 102 that are not coprime to 102, and so $\varphi(102)=102-70=32$.