Anonymous
Anonymous asked in Science & MathematicsMathematics · 4 weeks ago

co-prime numbers?

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

3 Answers

Relevance
  • 4 weeks ago
    Favorite Answer

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

    • Login to reply the answers
  • 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

    • ...Show all comments
    • 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.

    • Login to reply the answers
  • Anonymous
    4 weeks ago

    Tobias harris....

    • Login to reply the answers
Still have questions? Get your answers by asking now.