Anonymous
Anonymous asked in Science & MathematicsMathematics · 4 weeks ago

# co-prime numbers?

How many numbers lower than 2020 are relatively prime with 2020?

Relevance
• 4 weeks ago

That's the totient function ϕ(n).  Start with the prime factorization of n=2020:

2020 = 2^2 * 5 * 101

ϕ(2020) = 2020 * (1 - 1/2) * (1 - 1/5) * (1 - 1/101)

= 2020 * (1/2) * (4/5) * (100/101)

= 2020 * (400 / 1010)

= 800

That uses the formula for ϕ(n) as n times the product of (1 - 1/p_k) factors, where the p_k values are the *distinct* primes dividing n.  You don't need to know how many times each prime divides n.  That's "encoded" into the initial "n times".

• 4 weeks ago

2020 = 20 * 101 = 2^2 * 5 * 101

Any number that isn't a multiple of 2 , 4 , 5 , or 101 will be coprime

2020 * (1 - 1/4) * (1 - 1/5) * (1 - 1/101) =>

2020 * (3/4) * (4/5) * (100/101) =>

2020 * (3 * 4 * 100) / (4 * 5 * 101) =>

3 * 4 * 100 =>

1200

There are 1200 numbers that are relatively prime with 2020 that are between 1 and 2020

• husoski
Lv 7
4 weeks agoReport

Just stick to the single primes, though, and your analysis works and is equivalent to Euler's totient function.  20*(1 - 1/2)*(1 - 1/5) = 20 * (1/2) * 4/5) = 8.