Find all pairs of positive integers (m,n) for which there exist relatively prime integers a and b greater than 1 such that am+bman+bn is an integer.
Problem
Source: MEMO 2015, problem I-4.
Tags: number theory, relatively prime, Exponents, factorization, Euclidean algorithm
27.08.2015 18:58
The proof consists of three steps. (1) We cannot have 0<m<n. (2) We cannot have n<m≤2n. (3) If an+bn∣am+bm, then the same holds if we switch m to m−2n. From these, it follows that if some exponent m works, then its residue upon division by n (in range [1,2n]) works as well, and this residue can only be n because of (1-3). As a corollary, the solutions have the form ((2k−1)n,n) where k,n are arbitrary positive integers, and they work due to the result x+y∣x2k−1+y2k−1 (we may take arbitrary a,b). (1) is obvious because if 0≤m<n, then 0<am+bm<an+bn, thus it cannot be divisible by an+bn. Let d:=an+bn. Then we have the following: d∣am±bm⟹d∣am−n∓bm−n.(∗) This is true because am±bm∓bm−n(an+bn)=am∓bm−nan=an(am−n∓bm−n), where d and a are coprime as if they shared a prime divisor, it would also divide b. (2) follows because for n<m<2n, d∣am+bm implies d∣am−n−bm−n where 0<m−n<n. This shows that am−n−bm−n is non-zero, and that its absolute value is at most max, and hence it is not divisible by d, contradiction. (3) is an immediate corollary of (*) because d\mid a^m+b^m\implies d\mid a^{m-n}-b^{m-n}\implies d\mid a^{m-2n}+b^{m-2n}. Answer: (m,n)=((2k-1)n,n) with n,k positive integers.
27.08.2015 19:07
If m=n then this works, otherwise we clearly must have m > n Now, WLOG let b>a. Then a^n+b^n|a^m+b^m or a^n+b^n|b^m - b*a^{m-n} Now clearly gcd(a^n+b^n, b) = gcd(a^n,b) = 1 as a and b are relatively prime. Thus a^n+b^n | b^{m-1} - a^{m-n}. Applying the euclidean algorithm again we get a^n+b^n | a^n*b^{m-n-1} + a^{m-n}. That's what motivates us to look at 3 possibilities, m-n<n, m-n=n, m-n>n. Let's deal with the easiest one first, m-n=n. If this were the case then we would have a^n+b^n|a^n(b^{m-n-1} + 1). And, as before we have that (a^n+b^n , a^n) = 1 (where () means gcd) Thus a^n+b^n|b^{m-n-1} + 1. But we know that m=2n so this means a^n+b^n|b^{n-1}+1. And since a,b > 1 we have that a^n > 1 and b^n > b^{n-1} and thus b^{n-1} + 1 < a^n+b^n which is not possible as we need b^{n-1} + 1 \ge a^n + b^n Now, let's deal with m-n < n This is actually easier dealt with by looking back at the original equation. From a^n+b^n|a^m+b^m then a^n+b^n|b^m - b^n*a^{m-n} = b^n(b^{m-n} - a^{m-n}). From (a^n+b^n, b^n) = 1 we have a^n+b^n | b^{m-n} - a^{m-n}. Clearly 0 < b^{m-n} - a^{m-n} < b^n < a^n+b^n which is a contradiction Finally, let's deal with m-n > n We still have a^n+b^n | b^{m-n} - a^{m-n}. Now, applying the euclidean algorithm we have a^n+b^n | b^{m-n} + b^n * a^{m-2n} and again, we can divide LHS by b^n to get a^n + b^n | b^{m-2n} + a^{m-2n}. And this is where I get sniped. Sigh. Now, if m-2n < n then we're done and this is impossible. Thus, either m-2n = n or m = 3n (which is a solution) or m> 3n. Now, if m>3n we keep going to get a^n + b^n | b^{m-3n} - a^{m-3n}. Clearly, if m < 3n then we reach contradiction, and so we must have m > 3n in which case we may apply EA again to get a^n + b^n | b^{m-4n} + a^{m-4n}. Thus, in general, if (2k-1)n \le m < 2kn for some positive integer k then a^n+b^n | b^{m-(2k-2)n} + a^{m-(2k-2)n}, which we can prove through an easy induction. And from here, it is easy to see that unless m - (2k-2)n = n or m = (2k-1)n that we won't have a solution. Thus the answer, which is already stated above, is (m,n) = ((2k-1)n,n) where n and k are positive integers. Darn got sniped when i was almost done.
28.08.2015 17:42
My solution: We first prove that we must have n \mid m. Let m=cn+d with 0 \leq d < n and c>0, because obiously m \geq n. Then we get 0 \equiv a^m+b^m \equiv a^{cn+d}+b^{cn+d} \equiv a^d(-b^n)^c+b^{cn+d} \equiv b^{nc} (b^d \pm a^d) \pmod{a^n+b^n}. If d \not= 0, then 0<\left| a^d \pm b^d \right| < a^n+b^n, which is a contradiction. Hence d=0 and m=cn. Now we prove that c must be odd. Let A=a^n and B=b^n, then we get, if c were even, 0 \equiv A^c+B^c \equiv A^c + (-A)^c \equiv 2A^c \pmod{A+B}. If A+B had an odd prime divisor p, then we would have p \mid A and hence also p \mid B, which is a contradiction. Hence A+B must be a power of 2, which implies that A and B are both odd. But because A+B>2, we have 4 \mid A+B \mid 2A^c, hence A must also be even, which is absurd. Hence, it is necessary that m=cn for some odd positive integer c. Clearly this is also sufficient.
03.10.2015 19:44
Gryphos wrote: If d \not= 0, then 0<\left| a^d \pm b^d \right| < a^n+b^n, which is a contradiction. Hello, I do not understand how this is a contradiction, could you please explain? Thank you in advance!
03.10.2015 21:15
{}{}{}
04.10.2015 18:00
My solution: first set (m,n)=k m=pk n=qk and c=a^kd=b^k. We have c^q\equiv -d^q( mod c^q+d^q)c^p\equiv -d^p( mod c^q+d^q) now if we take x the smallest positive number such thatc^x\equiv -d^x( mod c^q+d^q) we get that if we set p=mx+gc^g\equiv d^g( mod c^q+d^q) which is contradiction because g\le x<2x so we get that x|p,x|q which is contradiction. Which now implies that q=1 . Also if we assume that p is even we get that c^p\equiv d^p\equiv -d^p(mod c^q+d^q) but we have that (c,d)=1.
30.08.2016 02:57
Setting m=un+v then plugging a^n \equiv -b^n \pmod{a^n+b^n}, we easily get v=0. Also, standard Euclidean Algorithm gives u \equiv 1 \pmod{2} so the answer is (n(2k+1),n).
11.01.2022 12:40
a^n+b^n|a^{m-2nk}+b^{m-2nk}Answer:(m,n)=(n(2k+1),n)
11.01.2022 12:40
very easy problem for p4