Determine all positive integers $n$ such that all positive integers less than $n$ and coprime to $n$ are powers of primes.
Problem
Source: Romania TST 2014 Day 2 Problem 3
Tags: number theory unsolved, number theory
21.01.2015 19:14
Let $ p1{}^n{}^1 $, $ p{}^n{}^2 $, ...$p{}^n{}^m$ be the powers of primes and are coprime to $ n $.Then according to the question we have that all $ pi $ are coprime to $ n $ but all numbers of the form $ pipj $ are not. So if $ p1 < p2 < p3 <.... < pm $, we must have that $ p1p2 > n $. Now if $ n = q1{}^l{}^1 . q2{}^l{}^2 ... qx{}^l{}^x$ Then $ p1 $ and $ p2 $ are at least the $ (x + 1)th $ and $ (x + 2)th $ primes respectively, and $ n $ is at least the product of the first $ x $ primes. Thus we must have that the product of the $ (x + 1)th $ and $ (x + 2)th $ primes is greater than the product of the first $ x $ primes, which is true only for $ x \geq 3 $(Similarly we also consider the cases when the power of one or more of the primes $ qi $ is greater than 1). the remaining $ should $ be trivial.
31.03.2015 20:48
Let me expand on AdithyaBhaskar's argument. Let $ n = \prod_{i = 1}^{\infty}p_i^{a_i} $ where $ p_i $ is the $ i $th prime and the $ a_i $ are nonnegative integers. Let $ r $ be the smallest positive integer for which $ a_r = 0 $ and let $ s $ be the second smallest positive integer for which $ a_s = 0. $ Then since $ \text{gcd}(p_rp_s, n) = 1 $ we must have $ p_rp_s > n \ge \frac{1}{p_r}\prod_{i = 1}^{s - 1}p_i. $ Call this the fundamental inequalityThis means that $ p_sp_{s - 1} > \prod_{i = 1}^{s - 2}p_i $ and a quick use of Bertrand's postulate shows that that this is true only when $ s \le 5. $ Now, assume there existed an integer $ t > s $ such that $ a_t \ne 0. $ Then we would need to have $ p_sp_{s - 1} > p_{s + 1}\prod_{i = 1}^{s - 2}p_i $ which again by Bertrand's postulate and some quick multiplication can only occur if $ n = 5 $ or if $ n = 14. $ Therefore, since we must have $ n < p_rp_s \le p_4p_5 = 77 $ we can just check all $ 76 $ cases. We find that the solution is $ \boxed{n \in \{1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 18, 20, 24, 30, 42\}} $
25.04.2016 16:56
Wolstenholme wrote: We find that the solution is $ \boxed{n \in \{1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 18, 20, 24, 30, 42\}} $ $n=60$ also satisfies the condition. I think you missed only this case.