For a natural number n, let ?(n) be the number of natural numbers less than or e

Question

For a natural number n, let ?(n) be the number of natural numbers less than or equal to n that are relatively prime to 3. Find the limit, with proof

problem 6. For a natural number n, let (n) be the number of natural numbers less than or equal to m that are relatively prime to 3. Find the limit, with proof, of (n) lim 000 problem 7. For a natural number n, let o(n) e the number of natural numbers less than or equal to n that are relatively prime to n. Prove that the limit lim n 00 does not exist.

Explanation / Answer

First note that for integer k with 1 k n, k is relatively prime to n if and only if n k is also relatively prime to n thus (n) = (n)*n /2 where (n) is Euler’s function and gives the number of positive integers less than or equal to n and relatively prime to n. Thus (n) = 3n if and only if (n) = 6. Let positive integer n = p r1 1 p r2 2 · · · p rm m where p1, p2, . . . , pm are distinct primes and r1, r2, . . . , rm are positive integers. It is well known that (n) = p r11 1 (p1 1)p r21 2 (p2 1)· · · p rm1 m (pm 1). It follows that if (n) = 6, then n can have no prime factor pk 8, so the only possible prime factors of n are 2, 3, 5, 7. If pk = 7 and rk 2, then (n) 7 21 (7 1) > 6, so the exponent on a prime factor of 7 can only be 0 or 1. If pk = 5, then (n) has a factor of 5 1 = 4, so no multiple of 5 is a candidate for n. If pk = 3 and rk 3, then (n) 3 31 (3 1) > 6, so the exponent on a prime factor of 3 can only be 0, 1, or 2. By similar reasoning, the exponent on a prime factor of 2 can only be 0, 1, 2, or 3. Thus, the only possible values of n are n = 2a3 b7 c where a = 0, 1, 2, 3, b = 0, 1, 2, and c = 0, 1. Because (n) = 6 means n 7, the possible values of n are 7, 8, 9, 12, 14, 18, 21, 24, 28, 36, 42, 56, 63, 72, 84, 126, 16, 252, 504. We can eliminate some of these by noting that n cannot be a multiple of both 3 and 7 because then (n) > 6. Eliminating multiples of 21 leaves the list 7, 8, 9, 12, 14, 18, 24, 28, 36, 56, 72. A quick check shows that (n) = 6 only for n = 7, 9, 14, 18.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.