WordGPT

Euler's totient: how many numbers up to 100 are coprime to 100?

Exercise · Level 3 (Medium)

Count the numbers from 1 to 100 that have no common factor with 100.

φ(100)= ?\varphi(100)=\ ?

wordgptpro.com

Solution

  1. A number shares a factor with 100 exactly when it is divisible by 2 or by 5. Among 100 numbers: 50 are even, 20 are multiples of 5, and 10 are multiples of 10 (counted twice).

  2. So the numbers divisible by 2 or 5 are 50+20−10=6050+20-10=60, leaving 100−60=40100-60=40. The same count as a formula:

    φ(100)=100(1−12)(1−15)=40\begin{aligned}&\varphi(100)\\&=100\left(1-\frac12\right)\left(1-\frac15\right)\\&=40\end{aligned}
    (1)
Answer4040

wordgptpro.com

Need a hint?

Remove the multiples of 2 and of 5, which are the prime factors of 100.

φ(100) = 40: forty of the numbers 1 to 100 are coprime to 100.

How to work it out

  1. A number shares a factor with 100 exactly when it is divisible by 2 or by 5. Among 100 numbers: 50 are even, 20 are multiples of 5, and 10 are multiples of 10 (counted twice).

  2. So the numbers divisible by 2 or 5 are 50+20−10=6050+20-10=60, leaving 100−60=40100-60=40. The same count as a formula:

    φ(100)=100(1−12)(1−15)=40\begin{aligned}&\varphi(100)\\&=100\left(1-\frac12\right)\left(1-\frac15\right)\\&=40\end{aligned}
    (1)
LaTeX source of the formulas on this page
\[ 40 \]
\[ \varphi(100)=100\left(1-\frac12\right)\left(1-\frac15\right)=40 \]

Questions

What is the answer to: Euler's totient: how many numbers up to 100 are coprime to 100??

φ(100) = 40: forty of the numbers 1 to 100 are coprime to 100.

What is the key idea?

Count by inclusion–exclusion: multiply by (1 − 1/p) for each prime factor p.

Is there a hint?

Remove the multiples of 2 and of 5, which are the prime factors of 100.

Related problems

More number theory problems

    Euler's totient: how many numbers up to 100 are coprime to 100?: answer and solution | WordGPT