Find all positive integers n such that for all positive integers m, 1<m<n, relatively prime to n, m must be a prime number.
Problem
Source: 2nd Final Mathematical Cup Senior Division P4 (2020)
Tags: number theory, relatively prime
01.10.2020 13:44
The answers are 1,2,3,4,6,8,12,18,24,30. For simplicity, we call such number cute. Claim. Let P be the set of primes dividing n. Let q be the smallest prime number that is not an element of P, then n is cute if and only if n<q2. Proof. If n is cute, then there must be no composite number pq where p,q primes such that (pq,n)=1. However, since we define q be the smallest prime number not in P, then n<q2 as well, or otherwise q2 satisfies (q2,n)=1. Now, if n<q2, then all of the composite numbers less than q2 must have a prime divisor in common with P, we are done. Now, we'll use the statement above for our proof. Using the same definition, we want to find all cute n. Fix an integer n. Then it must satisfy ∏p∈Pp<q2Suppose q=pk≥p5, by Bonne Theorem, we know that ∏p∈Pp≥p1p2…pk−1>p2kThus, q≤p4=7. If q=2, then n=1,3. If q=3, then n is a multiple of 2 less than 9, giving n=2,4,6,8. If q=5, then n is a multiple of 6 less than 25, giving n=6,12,18,24. If q=7, then n is a multiple of 30 less than 49, giving n=30. Remark. Bonne Theorem. Let p1=2<p2=3<… be a sequence of prime numbers. Then for all n≥4, p1p2…pn>p2n+1The proof of this is not difficult by induction. Base check is easily checked to be true. Now, notice that by Bertrand postulate on (pk+1,2pk+1) for k≥4, we get the bound pk+2<2pk+1. Thus, k+1∏i=1pi=pk+1⋅k∏i=1pi>pk+1p2k+1>4p2k+1=(2pk+1)2>p2k+2
01.10.2020 13:57
IndoMathXdZ wrote: The answers are 1,2,3,4,6,8,12,18,24,30. For simplicity, we call such number cute. Claim. Let P be the set of primes dividing n. Let q be the smallest prime number that is not an element of P, then n is cute if and only if n<q2. Proof. If n is cute, then there must be no composite number pq where p,q primes such that (pq,n)=1. However, since we define q be the smallest prime number not in P, then n<q2 as well, or otherwise q2 satisfies (q2,n)=1. Now, if n<q2, then all of the composite numbers less than q2 must have a prime divisor in common with P, we are done. Now, we'll use the statement above for our proof. Using the same definition, we want to find all cute n. Fix an integer n. Then it must satisfy ∏p∈Pp<q2Suppose q=pk≥p5, by Bonne Theorem, we know that ∏p∈Pp≥p1p2…pk−1>p2kThus, q≤p4=7. If q=2, then n=1,3. If q=3, then n is a multiple of 2 less than 9, giving n=2,4,6,8. If q=5, then n is a multiple of 6 less than 25, giving n=6,12,18,24. If q=7, then n is a multiple of 30 less than 49, giving n=30. Remark. Bonne Theorem. Let p1=2<p2=3<… be a sequence of prime numbers. Then for all n≥4, p1p2…pn>p2n+1The proof of this is not difficult by induction. Base check is easily checked to be true. Now, notice that by Bertrand postulate on (pk+1,2pk+1) for k≥4, we get the bound pk+2<2pk+1. Thus, k+1∏i=1pi=pk+1⋅k∏i=1pi>pk+1p2k+1>4p2k+1=(2pk+1)2>p2k+2 I found the same solution but was wondering if a solution that doesn't use Bertrand's postulate or Bonne's Theorem exists.
01.10.2020 15:47
The correct source for this problem is Chapter 27 ("A property of the number 30") of the book "The Enjoyment of Mathematics" by Hans Rademacher and Otto Toeplitz, published in 1933 by Springer, Berlin.