Find all odd positive integers n>1 such that if a and b are relatively prime divisors of n, then a+b−1 divides n.
Problem
Source:
Tags: number theory, relatively prime, Russia, Divisors, MONT
18.08.2007 13:29
See here http://www.mathlinks.ro/Forum/viewtopic.php?search_id=784323867&t=112155&sid=83def756750109c33923a40316d62c68 .
13.02.2012 12:59
We will prove that n is the power of an odd prime. 1) If possible, let n have 2 distinct prime divisors. Let p be the smallest (odd) prime dividing n. Then we may write n=pkm, with k and m positive integers, m>1 such that p∤. 2) p and m are relatively prime divisors of n, so p+m-1\mid n. We will show that p+m-1 is a power of p. Indeed, if m and p+m-1 had something in common then a prime divisor of m (say q) would divide p+m-1, but m<p+m-1<m+q, so p+m-1 can be caught between 2 consecutive multiples q, impossible. So take p+m-1=p^a for a a positive integer. 3) Again, p^a and m are relatively prime divisors of n. Hence p^a+m-1\mid n. But p^a+m-1=2p^a-p (by 2). So 2p^a-p\mid n=p^km, implying 2p^{a-1}-1\mid p^{k-1}m. As p and 2p^{a-1}-1 have nothing in common, we have 2p^{a-1}-1\mid m. 4) Using m=p^a-p+1, we get 2p^{a-1}-1\mid p^a-p+1\longrightarrow 2p^{a-1}-1\mid p(2p^{a-1}-1)-2(p^a-p+1)=p-2. But evidently, 2p^{a-1}-1>p-2, a contradiction. \blacksquare
09.07.2012 21:25
let n=P1^L1P2^L2...Ps^Ls such that Pi for alli is prime and let Pn>Pn-1>...>P2>P1 we know that P1+P2-1 divides n and easy to see P1+P2-1=P^r such that P is a prime number and we know that P<P2 because iff P=>P2 so ther exist number u for wich u divised P1+P2-1 and so u divised k such that k=<a-1 this is Contradiction. so s=<2 1-iff s=0 then n=1 2-iff s=1 then n=P^j such that 1<j 3-iff s=2 then n=p1^K1.P2^K2 such that P2=P1^t-P1+1
20.10.2012 23:55
Consider the smallest prime divisor of n, p. Let p^{e_1}|n with e_1 maximal. Then we have \frac{n}{p^{e_1}}+p-1 | n Since p-1 is relatively prime to n, and \frac{n}{p^{e_1}} has all prime divisors of n expect for p, \frac{n}{p^{e_1}}+p-1=p^{e_2} with e_2<e_1. Next we have that \frac{n}{p^{e_1}}+p^2-1|n if p^2|n. Then \frac{n}{p^{e_1}}+(p-1)(p+1). However, since p-1,p+1 are both relatively prime to n as n is odd, again we have that \frac{n}{p^{e_1}}+p^2-1=p^{e_3} with e_1>e_3>e_2. This means that p^{e_3}-p^{e_2}=p^2-p, which is only true for e_3=2 and e_2=1, or in fact \frac{n}{p^{e_1}}=1, implying that n is a power of p. If p^2 does not divide n, then \frac{n}{p^{e_1}}+p-1=p and we have the same result.
14.06.2015 15:22
Note: If we exclude the condition of being odd, then we also get 6, 12, 24 and 48 as solutions!
28.10.2015 06:03
Wait a minute, I don't see how 6,24,48 be solutions when 2+3-1 does not divide 6,2^3+3-1 does not divide 24,48. So, I would post my solution. We observe that if p \mid n and v_p(n)=x then \frac{n}{p^x}+p^x-1\mid p^{2x}-p^x. And AM-GM gives p^x>\sqrt[4]{n}. so n can't have more than 3. distinct prime factors. We consider the following three cases: Case 1. If n is a prime power. No work to do at all since these are solutions(yay).\square Case 2 If n=p^aq^b where p,q are distinct primes and a,b\ge 1. Assume w.l.o.g p<q. p+q-1\mid n and so since q can't p-1 we must have q=p^x-p+1 for some integer x\ge 2(Therefore, a\ge 2) Now, p^2+q-1 \mid n and so p^2+p^x-p divides n which means that since v_p(p^2+p^x-p)=1, we must have q \mid p+-1 and so p<q\le q+1 which means q=3,p=2. Now, 3=2^x-2+1 and so x=2. Moreover since if a>2 then 2^3+3-1 would dividen giving another prime factor and so a=2 and also b can be at most 1 since otherwise 2+3^2-1 \mid n gives another prime divisor. So only n=12 works in this case. Case-3 If n=p^aq^br^c where a,b,c\ge 1. and p,q,r are distinct primes. Assume w.l.o.g. p<q<r. Now, p+qr-1 \mid n and since q,r can't divide it so we must have qr=p^x-p+1 for some integer x. Moreover, p^x>qr>p^2 so x\ge 3. Now, p^2+qr-1=p^x-p^2+p=p(p^{x-1}-p+1) \mid n and therefore, a prime other than p divides p^2+qr-1. Sub case a.) If r divides p^2+qr-1. So r\mid p^2-1 and this gives p<q<r\le p+1. Clearly, a contradiction. Sub case b.) If q divides p^2+qr-1. This immediately gives q=p+1 and so p=2,q=3. Now, 2^3+3-1 \mid n and so r=5. However, 3+5-1=7 \mid n. giving another prime divisor a contradiction. So the only positive integers satisfying this are the prime powers and 12.\square.
28.10.2015 07:54
nice :v
19.03.2021 18:03
Gotta take this one back...
14.07.2021 22:04
My solution seems slightly sketchy... Could someone check whether it is correct or not? The answer is all p^k for odd prime p and k a positive integer. To check that these work, note that the factors are 1, p, p^2, ..., p^k. The pairs not including 1 aren't relatively prime, and it is clear that the pairs with 1 invovled work, so all of these satisfy the condition. Now we prove these are the only ones. Consider a number not in that form. Then it contains at least 2 distinct prime factors. Consider the largest two prime factors, let them be p and q where p > q. Then we know that p+q-1 | n. Notice that p+q-1 cannot be a prime factor of n because it is too large. This means that there exists another prime r where r<q such that r|p+q-1, or q|p+q-1. The second case is impossible because that would imply q|p-1, forcing q = 2. For the first case, we can deduce that r+p-1 is a factor of n, and is composite because r+p-1 > p but p is the largest prime factor. Therefore we can again have a prime s<r such that s|r+p-1, or r|r+p-1. We can see that because a number can only have a finite amount of prime factors, we will always reach a point where we have a prime factor equivalent 2. Therefore, numbers not in form p^k are impossible, so we are done. \blacksquare
18.08.2021 08:53
So as always choose N=p^k m with k \ge 1 and \gcd(m,p)=1 by the fundamental theorem of arithmetic. Now by the condition p+m-1|n. Note that:-\gcd(p+m-1,m)=\gcd(p-1,m)|\gcd(p-1,n)=1,thus p+m-1|p^k hence p+m-1=p^l for some l \le k Suppose that k \ge 2,then p^2+m-1|n and similarly \gcd(p^2+m-1,m)=\gcd(p^2-1,m)|\gcd(p^2-1,n)=1 As above,we deduce that p^2+m-1=p^j But we are already done since m-1=p^j-p^2=p^l-p Now since p^j-p^2=p^l-p=>p^2(p^{j-2}-1)=p(p^{l-1}-1),implying p|p^{l-1}-1 or l=1 with m=1,so if m>2 then the only solutions are odd powers of primes and clearly by a similar argument p works but p^2 doesn't,hence the answer is all odd powers of primes.
02.10.2021 20:34
What if a=7,b=9 and n=315,a+b-1=15|315,but 315 is not a prime power?? This sum is really meaningless.
10.12.2021 23:48
Claim: all n such that n is a power of an odd prime works Proof The multiset of factors of n is \{ 1, p, p^2, ... , p^k\} and choosing (a,b) = (1, p^m) for some 1 \leq m \leq k gives us \begin{align*} a+b-1 &= 1+p^m-1 \\ &= p^m | n \end{align*} Now, it suffices to show all n with more than 2 odd prime factors don't work. Assume for the sake of contradiction that n does. Let p, q be two distinct prime factors of n and let (a,b) = (p,q). We have p+q-1|n. Claim: There exists some prime r not equal to p,q such that r|p+q-1. Assume FTSOC that there doesn't exist such an r. Then, we must have the p+q-1 = \{1, p, q, pq\} as the set of cases. Clearly, the first three cases are impossible. If p+q-1 = pq , we have (p-1)(q-1)=0 , so p or q is 1. This is a contradiction. Therefore, our claim is true. By our claim, we have shown that n must have only one odd prime factor. We also showed that all such n with one odd prime factors work. Therefore, all n with one odd prime factor work. \blacksquare.
Edit: this is flawed. p+q-1=p^xq^y works
14.12.2021 05:53
minimal prime divisor.
24.01.2022 18:37
anantmudgal09 wrote: Wait a minute, I don't see how 6,24,48 be solutions when 2+3-1 does not divide 6,2^3+3-1 does not divide 24,48. So, I would post my solution. We observe that if p \mid n and v_p(n)=x then \frac{n}{p^x}+p^x-1\mid p^{2x}-p^x. And AM-GM gives p^x>\sqrt[4]{n}. so n can't have more than 3. distinct prime factors. We consider the following three cases: Case 1. If n is a prime power. No work to do at all since these are solutions(yay).\square Case 2 If n=p^aq^b where p,q are distinct primes and a,b\ge 1. Assume w.l.o.g p<q. p+q-1\mid n and so since q can't p-1 we must have q=p^x-p+1 for some integer x\ge 2(Therefore, a\ge 2) Now, p^2+q-1 \mid n and so p^2+p^x-p divides n which means that since v_p(p^2+p^x-p)=1, we must have q \mid p+-1 and so p<q\le q+1 which means q=3,p=2. Now, 3=2^x-2+1 and so x=2. Moreover since if a>2 then 2^3+3-1 would dividen giving another prime factor and so a=2 and also b can be at most 1 since otherwise 2+3^2-1 \mid n gives another prime divisor. So only n=12 works in this case. Case-3 If n=p^aq^br^c where a,b,c\ge 1. and p,q,r are distinct primes. Assume w.l.o.g. p<q<r. Now, p+qr-1 \mid n and since q,r can't divide it so we must have qr=p^x-p+1 for some integer x. Moreover, p^x>qr>p^2 so x\ge 3. Now, p^2+qr-1=p^x-p^2+p=p(p^{x-1}-p+1) \mid n and therefore, a prime other than p divides p^2+qr-1. Sub case a.) If r divides p^2+qr-1. So r\mid p^2-1 and this gives p<q<r\le p+1. Clearly, a contradiction. Sub case b.) If q divides p^2+qr-1. This immediately gives q=p+1 and so p=2,q=3. Now, 2^3+3-1 \mid n and so r=5. However, 3+5-1=7 \mid n. giving another prime divisor a contradiction. So the only positive integers satisfying this are the prime powers and 12.\square. Why n/p^x +p^x -1 | p^2x -p^x . Can u explain, please?
22.05.2022 17:27
Very cute problem! Let n=\prod_{k=1}^{t}p_k^{x_k} Also let a=p_1^{x_1}=\min \{p_k^{x_k} | 1 \le k \le t \} We choose a and \frac{n}{a} to be our a,b. a+\frac{n}{a}-1 | n \implies a^2-a+n | an \implies a^2-a+n | a^3-a^2\implies n \le a(a-1)^2 < a^3Also n > a^t. Therefore we have t<3 \implies t \in \{0,1,2\}For t=0, we have n=1 which is not desired as an answer. For t=1, we have n=p^x for odd primes p and positive integer x. For t=2, we take n=p^xq^y for distinct primes p,q. We assume p<q. Taking a,b as p,q, we see p+q-1 | n Thus q|p-1 which is absurd as p<q. Hence p+q-1 = p^z \implies q=p^z-p+1 Taking a,b as p^2,q we see p^2+q-1 | n Thus p^z+p^2-p | n \implies p^{z-1}+p-1 | n gcd(p^{z-1}+p-1,p^x)=1 Hence p^{z-1}+p-1=q^{\gamma}=(p^z-p+1)^{\gamma} Clearly z>1(else q=1). Checking (mod p) on this equation gives -1 \equiv 1 \mod p \implies p|2 which is a contradiction to the fact that p is odd. Hence the solution is the set \boxed{p^m | p \text{ is odd prime }, m \in \mathbb{N}}
05.11.2022 06:36
Really cool problem; the natural solution comes from using the condition n odd in a clever manner. The answer is powers of odd primes only, which clearly work. Now, let p_1 < p_2 < \cdots < p_k be the primes that divides n. Let \nu_{p_1}(n) = \alpha. By the given condition, p_1+\frac n{p_1^\alpha} - 1 divides n. Observe that by minimality, p_i \nmid p_1 - 1 for any i \geq 2. Thus, the expression must be a power of p_1 less than \alpha. If \alpha = 1, then n = p_1^\alpha, which is a contradiction. Else, we cleverly write p_i \nmid p_1^2 - 1 + \frac n{p_1^\alpha},as p_i \nmid p_1^2 - 1 in general as well. But now, this implies that p_1^2 - p_1 = p_1^{k_1} - p_1^{k_2}for some positive integers k_1, k_2. Obviously, (k_1, k_2) = (2, 1) is the only solution, but this yields n = p_1^\alpha again, contradiction.
30.07.2023 21:15
Assume that n has at least two prime divisor, and let p be the smallest among those and write n=p^\alpha m, where (p,m)=1. Then x\coloneq p+m-1\mid n. Suppose x has a prime divisor q\mid n not equal to p, which implies that q\mid m. Then we must have q\mid p-1, contradicting the minimality of p. Therefore, x must be a power of p. Then, write p+m-1=p^\beta. This forces p\mid m-1. However, then p^\beta+m-1=2p^\beta-p\mid p^\alpha m which implies 2p^{\beta-1}-1\mid m=p^\beta-p+1. But now, 2p^{\beta-1}-1\mid p(2p^{\beta-1}-1)-2(p^\beta-p+1)=p-2,which is clearly impossible.
24.10.2023 14:36
Nice problem. Let p be the smallest odd prime factor of n .Let n = p^{\alpha} m where p \nmid m Now note that p+m-1 \mid n so p+m-1 = p^k d where d is some factor of m and k is some natural number less or equal to \alpha Now we claim that d = 1 Proof : d \mid m and hence d \mid p+m-1 and hence d \mid p-1 so p-1\ge d and note that as d is odd (as n is odd ) it has to have some odd prime factor less than p and as d \mid n so it brings contradiction to the minimality of p . Now note that p+m-1 = p^k and so gcd(p+m-1,m) =1 and so p+2m-2 \mid n and similarly p+2m-2 = p^l 2p+2m-2 = 2p^k \implies p+2m-2 = p^l \implies p = 2p^k-p^l and p^l \mid p as p > 0 \implies 2p^k > p^l \implies p^k \ge p^l and so l =1= k by comparing the powers of p in lhs and rhs and note that l ,k can not be 0. and so p+m-1 = p and so m=1 and hence proved that n= p^{\alpha}
24.01.2024 20:45
Let n=p^\alpha\cdot k with p being the smallest prime divisor of n (p,k)=1\hspace{0.2cm} \Rightarrow\hspace{0.2cm} p+k-1\mid n\hspace{0.2cm}\Rightarrow\hspace{0.2cm} p+k-1=p^\theta\cdot k_1\hspace{0.2cm} \Rightarrow\hspace{0.2cm} k_1\mid p+k-1 \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \boxed{k_1\mid p-1\hspace{0.2cm} \text{and} \hspace{0.2cm} k_1\mid n}Which implies k_1=1 because the minimality of p, so p+k-1=p^\theta (p+k-1,k)=1 \hspace{0.2cm}\Rightarrow\hspace{0.2cm} p+2k-2\mid n \hspace{0.2cm}\text{Anagously}\hspace{0.2cm} p+2k-2=p^\gammaso, by p+k-1=p^\theta and p+2k-2=p^\gamma we get p=2p^\theta-p^\gamma \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \theta=\gamma=1 so k=1 and \boxed{n=p^\alpha}
28.05.2024 02:05
I claim that all positive integer powers of odd primes only work. Indeed, verifying this claim is true. Let p, q be primes that divide an integer n with p the smallest prime dividing n. Then observe that q \equiv 1 \pmod p and p \equiv 1 \pmod q. However the second congruence would yield p = 1, so we only have q \equiv 1 \pmod p. Then q = pk + 1, for some k \in \mathbb{Z^+}. Then p + q - 1 = p(k + 1) \mid n, and we must have k + 1 \geq p, or else this contradicts the minimality of p. Hence k + 1 = p^a N, for N is odd and divides n while p \nmid N. Then \begin{align*} pk + 1 &= p(p^aN - 1) + 1 \\ &= p^{a + 1}N - p + 1 \\ \implies q + p - 1 &= p^{a + 1}N, \text{ and } N \geq q \\ \implies q + p - 1 &= p^{a + 1}N \geq p^{a + 1}q, \end{align*}which is a contradiction for p, q > 2. Hence k + 1 = 1, so that q = 1, and the only prime that divides n is p, in particular, n = p^m, for some positive integer m. \blacksquare
10.06.2024 11:58
We claim that n is any power of an odd prime. We prove these satisfy the conditions. Let n = p^k. Since any divisor of n is of the form p^i, it will only be coprime to 1. Since, p^i + 1 -1 = p^i \mid p^kWe prove these satisfy the conditions. Now we prove these are the only ones. We assume for the sake of contradiction that n = p^{\alpha}m where p is the smallest prime divisor of n. Since p is coprime to m, p + m -1 \mid n = p^{\alpha}m \textbf{Claim 1}: We claim that \gcd(p+k(m-1),m) = \gcd(p-k,m) = 1 for 1\leq k <p. We know that prime factorisation of p-k contains all the primes < p whereas m conatins all the primes > p because p was assumed to be the smallest prime divisor of n. So, our claim follows. From our claim we can say that, p + m -1 \mid p^{\alpha}. Now we can write \begin{align} p + m -1 = p^{\beta} \text{ where } 1<\beta\leq \alpha \end{align} Since \gcd(p^{\beta}, m) = 1 so, p^{\beta} + m-1\mid p^{\alpha}mSubstituting the value of p^{\beta} we get, p + 2(m-1)\mid p^{\alpha}mFrom our claim, \gcd(p+2(m-1), m) = 1, so p +2(m+1)\mid p^{\alpha}From equation (1) we get, 2p^{\beta} - p \mid p^{\alpha}2p^{\beta -1} -1\mid p^{\alpha -1}which is a contradiction! Hence, n is any power of an odd prime.
07.07.2024 07:14
We claim n is the power of an odd prime. Clearly these work. Assume FTSOC n has \geq 2 prime factors. Let p\geq 3 be the smallest prime factor of n. Let n=:p^km for k,m\in\mathbb{Z}^+ where p\nmid m. Note that m>1. Then m+p-1 divides n. Since \gcd(m,m+p-1)=\gcd(m,p-1)=1 by the minimality of p, it follows that m+p-1=p^l for a positive integer 2\leq l\leq k. Since m+p^k-1=p^k+p^l-p divides n, it follows that p^{k-1}+p^{l-1}-1\mid n. Since p is relatively prime with p^{k-1}+p^{l-1}-1, it follows that p^{k-1}+p^{l-1}-1\mid m=p^l-p+1. By size reasons, we must have l=k. Hence 2p^{k-1}-1\mid p^k-p+1 so (2p^{k-1}-1)d=p^k-p+1. Since k\geq 2, taking mod p gives d\equiv -1\pmod{p} so d\geq p-1. It follows that p^k-p+1\geq(p-1)(2p^{k-1}-1) so p\leq 2, a contradiction. \square
29.07.2024 20:43
anantmudgal09 wrote: Wait a minute, I don't see how 6,24,48 be solutions when 2+3-1 does not divide 6,2^3+3-1 does not divide 24,48. So, I would post my solution. We observe that if p \mid n and v_p(n)=x then \frac{n}{p^x}+p^x-1\mid p^{2x}-p^x. And AM-GM gives p^x>\sqrt[4]{n}. so n can't have more than 3. distinct prime factors. We consider the following three cases: Case 1. If n is a prime power. No work to do at all since these are solutions(yay).\square Case 2 If n=p^aq^b where p,q are distinct primes and a,b\ge 1. Assume w.l.o.g p<q. p+q-1\mid n and so since q can't p-1 we must have q=p^x-p+1 for some integer x\ge 2(Therefore, a\ge 2) Now, p^2+q-1 \mid n and so p^2+p^x-p divides n which means that since v_p(p^2+p^x-p)=1, we must have q \mid p+-1 and so p<q\le q+1 which means q=3,p=2. Now, 3=2^x-2+1 and so x=2. Moreover since if a>2 then 2^3+3-1 would dividen giving another prime factor and so a=2 and also b can be at most 1 since otherwise 2+3^2-1 \mid n gives another prime divisor. So only n=12 works in this case. Case-3 If n=p^aq^br^c where a,b,c\ge 1. and p,q,r are distinct primes. Assume w.l.o.g. p<q<r. Now, p+qr-1 \mid n and since q,r can't divide it so we must have qr=p^x-p+1 for some integer x. Moreover, p^x>qr>p^2 so x\ge 3. Now, p^2+qr-1=p^x-p^2+p=p(p^{x-1}-p+1) \mid n and therefore, a prime other than p divides p^2+qr-1. Sub case a.) If r divides p^2+qr-1. So r\mid p^2-1 and this gives p<q<r\le p+1. Clearly, a contradiction. Sub case b.) If q divides p^2+qr-1. This immediately gives q=p+1 and so p=2,q=3. Now, 2^3+3-1 \mid n and so r=5. However, 3+5-1=7 \mid n. giving another prime divisor a contradiction. So the only positive integers satisfying this are the prime powers and 12.\square. How did you find that p^x>\sqrt[4]{n} ???
22.10.2024 15:11
We claim that n is a power of an odd prime, or n = p^k where p is some prime, for some positive integer k. Note that this solution works: p^t+1-1 = p^t|n=p^k for t \le n (note that: (p^t, 1)=1). FTSOC, assume that n=p^a m where p is the smallest prime divisor of n and p \nmid m, where a is some positive integer. Consider p+m-1|n. Since (m, p+m-1) = (m, p-1) = 1 as p is the smallest prime divisor of n, p+m-1=p^t for some integer t \le a. Note that: m=p^t-p+1. Thus: m+p^a-1 = p^t+p^a-p|n which implies: p^{t-1}+p^{a-1}-1|n = p^a m \implies p^{t-1}+p^{a-1}-1|m = p^t-p+1. Due to the size argument: we should have t=a (consider t \le a-1 which implies p^{a-2}+p^{a-1}-1 \ge p^{t-1}+p^{a-1}-1 > p^{a-1}-p+1 which doesnt satisfy the condition). Thus: 2 \cdot p^{a-1}-1| p^{a}-p+1.Note that: p^{a}-p+1 = d \cdot (2 \cdot p^{a-1}-1). Considering \pmod p we have: d \equiv -1 \pmod p which implies d \ge p-1. Therefore: p^{a}-p+1 = d \cdot (2 \cdot p^{a-1}-1) \ge (p-1)(2 \cdot p^{a-1}-1) which implies p \le 2. Thus, we have contradiction.