Imo Shortlist Problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Imo Shortlist Problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IMO Shortlist 2000, Problem N4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

42 posts

Lopes

#1 h Feb 27, 2005, 7:13 PM • 6 Y

Y by itslumi, FaThEr-SqUiRrEl, Adventure10, Mango247, and 2 other users

Find all triplets of positive integers $(a,m,n)$ such that $a^m + 1 \mid (a + 1)^n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

484 posts

Davron

#2 h Jun 5, 2006, 12:48 AM • 5 Y

Y by mathisreal, FaThEr-SqUiRrEl, Adventure10, Mango247, and 1 other user

Answer: (a, m, n) = (1, m, n), (a, 1, n) or (2, 3, k) where k > 1.

It is obvious that (1, m, n) and (a, 1, n) are solutions, so assume a > 1 and m > 1. We show first that m must be odd.

Suppose there is an odd prime p dividing am + 1. Then p must also divide (a + 1)n and hence (a + 1). So a = -1 mod p, so am + 1 = (-1)m + 1 mod p. Hence m is odd. If there is no such prime p, then am + 1 = 2k for some k. But a and m are assumed to be at least 2, so am + 1 must be at least 5 and hence k ≥ 3. So am = -1 mod 4. But squares can only be 0 or 1 mod 4, so am cannot be a square, so m must be odd.

Suppose p divides m. Then (since m is odd) ap + 1 divides am + 1 and hence (a + 1)n. But p is odd, so a + 1 divides ap + 1 and (ap + 1)/(a + 1) = ap-1 - ap-2 + ap-3 - ... - p + 1 divides (a + 1)n-1. Put f(x) = xp-1 - xp-2 + ... - x + 1. Then f(-1) = p, so f(x) - p = (x + 1) g(x) for some polynomial g(x). Putting x = a, we get f(a) = (a + 1) g(a) + p. If a prime q divides f(a), then since f(a) divides (a + 1)n-1, q must divide (a + 1). Hence q divides p, so q = p. So f(a) = pk for some k ≥ 1. Since f(a) divides (a + 1)n-1, p must divide a + 1.

We show next that k = 1, so f(a) = p. If p2 divides (a + 1), then f(a) = (a + 1) g(a) + p implies that p2 does not divide f(a). If p2 does not divide (a + 1), then (a + 1) = ph (with h not divisible by p). So f(a) = (ap + 1)/(a + 1) = ( (1 + ph - 1)p)/ph = ( 1 - 1 + p2h + terms divisible by p3)/ph = p mod p2, so again p2 does not divide f(a). So in any case f(a) = p.

Now (a2 - a) ≥ 2, (a4 - a3) ≥ 8 and obviously (a2r - a2r-1) ≥ 2 for r ≥ 2. So f(a) ≥ 11 > 5 for p = 5, and hence by a trivial induction f(a) > p for p > 5. So the only possibility is p = 3. Then we have a2 - a + 1 = 3 and hence a = 2.

So far we have established that a = 2 and that m is a power of 3. But (29 + 1) = 513, which is not a power of 3 and so cannot divide (2 + 1)n. But (227 + 1), (281 + 1), ... are all divisible by (29 + 1) and hence are also not powers of 3. So m must be 3. Finally, we require that (am + 1) = 9 divides (2 + 1)n, so n ≥ 2.

davron ft. kalva

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

36 posts

trigg

#3 h Jun 20, 2009, 7:52 AM • 3 Y

Y by FaThEr-SqUiRrEl, Adventure10, Mango247

I think this problem is not hard but it is nice

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7579 posts

ZetaX

#4 h Jun 20, 2009, 10:38 AM • 3 Y

Y by FaThEr-SqUiRrEl, Adventure10, Mango247

Like the similar ones just a corollary of Zsigmondy's theorem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11 posts

#5 h Jun 25, 2012, 4:31 AM • 2 Y

Y by FaThEr-SqUiRrEl, Adventure10

If a=1 then 〖 1〗^m+1|〖(1+1)〗^n this means for all m,n∈Z^+ and a=1 is solution. If a=2 and m=3 then 〖 2〗^3+1|3^n this means a=2 m=3 and for all n≥2 and n∈Z^+ is solution.If m=1 then for all a,n∈Z^+ is solution. If (a,m)≠(2,3) and a≠1 and m≠1 then from the Zsigmondy theorem ∃p∈prime p|a^m+1 but p∤a+1 this means contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

547 posts

#6 h Aug 22, 2012, 4:57 AM • 6 Y

Y by Max D.R., nguyendangkhoa17112003, FaThEr-SqUiRrEl, Adventure10, Mango247, and 1 other user

Quick way to start the proof before some cases:
Solution outline

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

485 posts

#7 h Jun 6, 2013, 5:15 PM • 3 Y

Y by FaThEr-SqUiRrEl, DCMaths, Adventure10

If $m$ is even, the any prime $p|a+1$ or $a\equiv -1\pmod{p}$ and $a^m+1\equiv 2\pmod{p}$ . If $a+1$ is a power of $2$ , then we have a contradiction as primes other than $2$ divide $a^m+1$ unless $a^m+1=2$ , which means $a=1$ and discounts the case otherwise.

For $m$ odd, $a+1 | a^m+1$ and any prime divisor of $a^m+1$ divides $(a+1)^n$ , implying all prime divisors of $a^m+1$ divides $a+1$ . By LTE if a prime $p$ divides $a+1$ , then $v_p(a^m+1)=v_p(a+1)+v_p(m)$ . Therefore if all the prime divisors of $a+1$ are the prime divisors of $a^m+1$ , and the $v_p$ of any prime dividing $a^m+1$ divides $m$ , $\frac{a^m+1}{a+1} | m$ .

If $m=1$ obviously all $a$ and $n$ work. If $a=1$ clearly all $m,n$ work. If $m>3$ the $\frac{a^m+1}{a+1}>m$ for $a\ge 2$ . If $m=3$ the only solution is $a=2$ otherwise $\frac{a^m+1}{a+1}>m$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sayantanchakraborty

505 posts

sayantanchakraborty

#8 h May 20, 2014, 6:16 PM • 7 Y

Y by Sx763_, FaThEr-SqUiRrEl, ZHEKSHEN, NVA9205, Adventure10, Mango247, panche

It is easy to note that $(a,m,n)=(1,m,n)$ is a solution.Let $a \ge 2$ .Also suppose $m \ge 2$ and $(a,m) \neq (2,3)$ .Then by Zsigmondy's theorem there exists a primitive prime factor of $a^m+1$ which does not divide $(a+1)$ and hence doesn't divide $(a+1)^n$ .For $m=1$ we get the trivial solution $(a,1,n)$ .For $a=2,m=3$ the condition is true for $n \ge 2$ so $(2,3,n \ge 2)$ are also solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1000 posts

#9 h Mar 23, 2017, 2:51 PM • 2 Y

Y by FaThEr-SqUiRrEl, Adventure10

Too easy problem.
$(a,m,n)=(1,m,n),(2,3,n)$
It is obvious that $m$ is odd. İf $m$ is even:
Take $p|a^m+1$ then $p|a+1$ or $a\equiv -1 mod p$ $a^m+1\equiv (-1)^m+1 mod p$ . Contradiction.
Claim: $a^m+1$ and $a+1$ have the same prime divisors.
Proof:Take an arbitrary $p|a^m+1$ then $p|(a+1)^n$ since $p$ is prime $p|a+1$ .

By Zsigmondy's theorem there is $q|a^m+1$ but not $q|a+1$ .Contradiction.

Comment

This post has been edited 2 times. Last edited by tenplusten, Mar 24, 2017, 5:10 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

820 posts

#10 h Aug 14, 2019, 4:13 PM • 3 Y

Y by FaThEr-SqUiRrEl, Adventure10, Mango247

Wait Zsigmondy was still so unpopular even as late as $2000$ ? (as this is not even a one-liner using Zsigmondy and its exceptions)...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2125 posts

#12 h Apr 18, 2020, 6:03 PM • 1 Y

Y by FaThEr-SqUiRrEl

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

429 posts

R-sk

#13 h Dec 10, 2020, 6:17 AM • 1 Y

Y by FaThEr-SqUiRrEl

Here since we can easily find the trivial solutions then by zsigmondy there exist a divisor of a^m+1 that does not divide a+1 and therefore does not divide (a+1) ^n and therefore there are no other solutions other than (1, m, n), (2, 3,n), (a, 1,n)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

396 posts

#14 h Apr 9, 2021, 4:49 AM • 1 Y

Y by FaThEr-SqUiRrEl

N5 is also an application of Zsimondy's..

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

113 posts

#15 h Apr 20, 2021, 1:22 PM • 1 Y

Y by FaThEr-SqUiRrEl

This can be trivialized by Zsigmondy's.

ISL 00N4. Find all $(a, m, n)\in\mathbb{N}^3$ such that $a^m+1\mid (a+1)^n$ .

Solution. If $a=1$ then the divisibility condition obviously work. Assume now that $a\ge 2$ .
If $m=1$ then the divisibility condition obviously work. Assume now that $a\ge 2$ , $m\ge 2$ .
If the two conditions $a=2$ , $m=3$ are not both true then by Zsigmondy's there must exist a prime factor $p$ of $a^m+1$ which does not divide $a+1$ (and of course so does not $(a+1)^n$ ). Hence there is no solution in this case.
It suffices for us to consider the single case $a=2$ , $m=3$ , in which only all $n\ge 2$ satisfy the divisibility condition.
Therefore the solutions are only $(1, m, n), (a, 1, n), (2, 3, k)$ where $k\ge 2$ .

This post has been edited 4 times. Last edited by isaacmeng, Apr 20, 2021, 1:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

429 posts

hakN

#16 h Apr 20, 2021, 6:40 PM • 4 Y

Y by FaThEr-SqUiRrEl, Mango247, Mango247, Mango247

If $a=1$ then we get $(1,m,n)$ as solutions for all $m,n\in \mathbb{N}$ .
If $a=2$ then we get that $2^m + 1\mid 3^n$ . If $m=1$ then we get $(2,1,1)$ as a solution. If $m\geq 2$ , then $2^m + 1 = 3^k$ doesnt have any solution except $(m,k)=(3,2)$ becuase of Mihailescu's Theorem.

Let $a\geq 3$ and $m\geq 2$ . By Zsigmondy, $a^m + 1$ has a prime divisor that doesnt divide $a+1$ . Thus, if we take that divisor we clearly get no solution. If $m=1$ then we get $(a,1,n)$ as solutions.
So all solutions are $(1,m,n) , (a,1,n) , (2,3,n)$ .

This post has been edited 2 times. Last edited by hakN, Apr 20, 2021, 6:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1746 posts

oVlad

#17 h Oct 21, 2021, 9:21 AM

Y by

Here's another way to solve this without Zsigmondy:

If $p\mid a^m+1$ then $p\mid (a+1)^n$ so $p\mid a+1$ so $\nu_p(a^m+1)=\nu_p(a+1)+\nu_p(m)\leq \nu_p(a+1)\big(\nu_p(m)+1\big)\leq \nu_p(a+1)\big(\log_2 m+1\big)$ Hence, we gat that $a^m+1\mid (a+1)^{\log_2 m+1}$ so $(a+1)^{\log_2 m+1}\geq a^m+1.$ However, by Holder's Inequality, we get that $2^{\log_2 m+1}\big(a^{\log_2 m+1}+1\big)\geq (a+1)^{\log_2 m+1}\geq a^m+1$ so by letting $\log_2 m=c$ we essentially got that $2^{c+1}\big(a^{c+1}+1\big)\geq a^{2^c}+1$ which, after some easy bounding, will give us $a=1, m=1$ or $a,m\leq 3.$

This post has been edited 2 times. Last edited by oVlad, Oct 21, 2021, 9:21 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1562 posts

#18 h Oct 21, 2021, 11:53 AM

Y by

Sorry for using Zsigmondy when almost everyone did :blush:

:blush:

, i just couldnt resist the free problem xD

Case 1: $m=1$
Then $a+1 \mid (a+1)^n$ which holds for any $a,n \in \mathbb N$ thus $(a,m,n)=(a,1,n)$
Case 2: $a=1$
Then $2 \mid 2^n$ which holds for any $m,n \in \mathbb N$ thus $(a,m,n)=(1,m,n)$
Case 3: $a,m>1$
Since $\gcd(a,1)=1$ we can use Zsigmondy assuming that $(a,m) \ne (2,3)$ so let $p$ such that $p \mid a^m+1$ and $p \not \; \mid a+1$ but since $p \mid a^m+1 \mid (a+1)^n$ we get a contraidiction.
Thus $a=2$ and $m=3$ and since $9 \mid 3^n$ holds for $n \ge 2$ the sol is $(a,m,n)=(2,3,n)$ where $n>2$

Thus we are done :blush:

:blush:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1080 posts

#19 h Nov 19, 2021, 2:56 AM • 1 Y

Y by centslordm

By Zsigmondy, $a^m+1$ has a primitive prime factor if $(a,m)\neq(2,3);$ let the prime be $p.$ If $m>1$ and $a>1,$ $p\nmid a+1,$ so $a^m+1\nmid (a+1)^n.$ If $a=1$ or $m=1,$ notice that $1+1\mid 2^n$ and $a+1\mid(a+1)^n,$ respectively. If $(a,m)=(2,3)$ and $n>1,$ we have $2^3+1\mid(2+1)^n,$ so our solutions are $\boxed{(a,1,n),(1,m,n)},$ and $\boxed{(2,3,n)\text{ where }n>1}.$ $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

435 posts

#20 h Apr 1, 2022, 3:02 AM

Y by

We divide in two cases.

1) $m$ is even.
In this case, we have that if $p \mid a+1$ , then $p \mid a^m + 1$ , therefore $p \mid 2$ since $m$ is even. So we get $a^m + 1 = 2^x$ for some $x$ , but notice that $4 \nmid a^m + 1$ so we conclude $x=1, a=1$ . In this case we get the solution $(a,n,m) = (a,2m',n)$ for any $m',n$ positive integers.

2) $m$ is odd. In this case, we have that $a+1 \mid a^m + 1$ . So we get that $\dfrac{a^m + 1}{a+1} \mid (a + 1)^{n-1}$ . Notice that $\dfrac{a^m + 1}{a+1} = a^{m-1} - a^{m-2} + \dots + 1$ is odd since $m$ is odd and therefore it has no factors $2$ .

So we can apply the LTE Lemma, which concludes that $\nu_p(\dfrac{a^m + 1}{a+1}) = \nu_p(m)$ for every prime $p$ that divides $\dfrac{a^m + 1}{a+1}$ (which are almost all the same primes that divide $a^m + 1$ , the same as the ones that divide $a+1$ ). But this clearly implies that $\dfrac{a^m + 1}{a+1} \mid m$ . Looking at the size of the left hand size, we get that either $a=1$ , $m=3$ or $m=1$ . If $a=1$ , we get the solution $(a,n,m) = (1,n,2m'+1)$ for any $m',n$ positive integers. If $m=3$ , we either have $a=2$ or $a=1$ . If $a=1$ we are already done, and if $a=2$ we get that $n=2$ so we get the solution $(a,n,m) = (2,2,3)$ . Finally, when $m=1$ we get the solution $(a,n,m) = (a,n,1)$ for any $a,n$ positive integers.

Finally, we get that the solutions are $(a,n,m) = (2,2,3), (1,n,m), (a,n,1)$ .

This post has been edited 1 time. Last edited by hydo2332, Apr 1, 2022, 3:03 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1746 posts

awesomeming327.

#21 h Jun 25, 2022, 2:53 AM

Y by

oof^tm

Note that $(a,1,n)$ , $(1,m,n)$ and $(2,3,n),n\ge 2$ are solutions. We claim that these are the only solutions. Suppose $a,m>1.$ Then, $n=1$ clearly doesn't work so $n>1$ as well. Also remove case $(2,3,n).$ By Zsigmondy's there exists a prime factor of $a^m+1$ that doesn't divide $a+1$ so it doesn't divide $(a+1)^n$ as well. Thus, we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5610 posts

#22 h Jul 9, 2022, 2:30 AM

Y by

The only solutions are $\boxed{(1,m,n), (a,1,n), (2,3,n+1)}$ , where $a$ , $m$ , and $n$ are any positive integers.

The first one works because the LHS is $2$ , the RHS is $2^n$ , and $2\mid 2^n$ .

The second one works because the LHS is $a+1$ , the RHS is $(a+1)^n$ , and $a+1\mid (a+1)^n$ .

The third one works because the LHS is $9$ , the RHS is $3^{n+1}$ . Since $n+1\ge 2$ , $9\mid 3^n$ .

It remains to show that those are the only solutions.

If $a=1$ , we get the solution $(1,m,n)$ .

If $m=1$ , we get the solution $(a,1,n)$ .

Now suppose $a>1$ and $m>1$ .

If $a=2$ and $m=3$ , then we have $9\mid 3^n$ , so $n\ge 2$ , which gives the solution $(2,3,n+1)$ .

Otherwise, by Zsigmondy's, there exists a prime divisor of $a^m+1$ that doesn't divide $a+1$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8880 posts

#23 h Jul 20, 2022, 4:01 PM • 2 Y

Y by awesomeming327., Ritwin

I suppose here's a more instructive solution that isn't some variant of "trivial by Zsigmondy's."

The answers are $(1, m, n)$ , $(2, 3, n)$ , and $(a, 1, n)$ , which work. Henceforth assume that $a, m > 1$ and $a \neq 2$ . It suffices to show that $a^m+1$ contains a prime factor that does not divide $a+1$ for all choices of $a$ and $m$ .

Observe that it suffices to show the case for $m$ a prime number $p$ , as $\nu_p(a^m + 1) = \nu_p(a^{m/k} + 1) + \nu_p\left(\frac mk\right) > 0$ for any $p \mid a^{m/k} + 1$ by choosing $\frac mk$ prime. In particular, we may choose $p \nmid a+1$ because the hypothesis holds for $\frac mk$ prime.

Now let $m$ be a prime number $p_1$ . For any $p \neq p_1$ that divides $a+1$ , $\nu_p(a^{p_1} + 1) = \nu_p(a+1) + \nu_p(p_1) = \nu_p(a+1)$ by LTE, and furthermore if $p_1$ also divides $a+1$ , $\nu_{p_1}(a^{p_1} + 1) = 2$ in this case as well. Suppose that $m$ has no prime factors that do not divide $n$ ; then, $a^m+1 \leq (a+1)^2$ with equality holding when $a = p_1$ is prime and $m=p_1$ . This forces $m=1, 2$ (and also the weird case $m=3, a=2$ ), from where we can check the cases manually. Otherwise, there must exist some $p$ that divides $a^m+1$ but not $n$ , so the hypothesis is true and we are done.

This post has been edited 1 time. Last edited by HamstPan38825, Jul 20, 2022, 4:02 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1930 posts

#24 h Aug 13, 2022, 5:11 PM

Y by

Solved with a hint from Ritwin.

For this to be possible, for all $p$ such that $p|a^m+1$ , it must also have $p|(a+1)^n\Rightarrow p|a+1$ . However, that is impossible by a variation of Zsigmondy's that says that $a^n+b^n$ has at least one primitive prime divisor with exceptions $2^3+1^3$ and trivial cases. The trivial cases are when $a=1$ and when $m=1$ . Therefore, our answers are $(2,3,n)$ where $n\ge2$ , $(1,m,n)$ for positive integers $m,n$ , and $(a,1,n)$ for positive integers $a,n$ .

This post has been edited 1 time. Last edited by cj13609517288, Aug 13, 2022, 5:24 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

39 posts

Msn05

#25 h Oct 29, 2022, 10:21 AM • 2 Y

Y by Ibrahim_K, teomihai

The answer is $(a,1,n), (1,m,n)$ and $(2,3,n)$ for $n \geq 2$ .
Case 1: $m$ is even.
Notice we want to get $\gcd(a^m+1,(a+1)^n)=a^m+1$ but we have at most $\gcd(a^m+1,(a+1)^n)=2$ (When $a$ is odd). So, $a=1$ since $a \geq 2$ is impossible.
From here we get $(a,m,n)=(1,m,n)$ (Also works for all $m$ ).
Case 2: $m$ is odd.
$m=1$ obviously works. So from here $(a,m,n)=(a,1,n)$ .
Now assume $m>1$ . We want to get $\gcd(a^m+1,(a+1)^n)=a^m+1$ but we have $\gcd(a^m+1,(a+1)^n)=\gcd(m(a+1),(a+1)^n)$ . After proving by induction we have $a^m+1 \geq am+m$ for all $a \geq 2$ and $m\geq 3$ so we need to solve $m(a+1)=a^m+1$ and from here we get $m \mid a^m+1$ . So, $a$ and $m$ are coprime and thus we have $a^m \equiv -1 \pmod{m}$ , $a^{2m} \equiv 1 \pmod{m}$ and $a^{\varphi(m)} \equiv 1 \pmod{m}$ . So
from Zsigmondy's Theorem we get $a=2,m=3$ . And thus we have $(a,m,n)=(2,3,n)$ for $n \geq 2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2967 posts

#26 h Nov 13, 2022, 2:01 PM

Y by

Msn05 wrote:

The answer is $(a,1,n), (1,m,n)$ and $(2,3,n)$ for $n \geq 2$ .
Case 1: $m$ is even.
Notice we want to get $\gcd(a^m+1,(a+1)^n)=a^m+1$ but we have at most $\gcd(a^m+1,(a+1)^n)=2$ (When $a$ is odd). So, $a=1$ since $a \geq 2$ is impossible.
From here we get $(a,m,n)=(1,m,n)$ (Also works for all $m$ ).
Case 2: $m$ is odd.
$m=1$ obviously works. So from here $(a,m,n)=(a,1,n)$ .
Now assume $m>1$ . We want to get $\gcd(a^m+1,(a+1)^n)=a^m+1$ but we have $\gcd(a^m+1,(a+1)^n)=\gcd(m(a+1),(a+1)^n)$ . After proving by induction we have $a^m+1 \geq am+m$ for all $a \geq 2$ and $m\geq 3$ so we need to solve $m(a+1)=a^m+1$ and from here we get $m \mid a^m+1$ . So, $a$ and $m$ are coprime and thus we have $a^m \equiv -1 \pmod{m}$ , $a^{2m} \equiv 1 \pmod{m}$ and $a^{\varphi(m)} \equiv 1 \pmod{m}$ . So
from Zsigmondy's Theorem we get $a=2,m=3$ . And thus we have $(a,m,n)=(2,3,n)$ for $n \geq 2$ .

BEAUTIFUL TREATMENT OF CASES!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

662 posts

#27 h Mar 24, 2023, 6:33 PM

Y by

Overkill
Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

347 posts

#28 h May 18, 2023, 1:48 AM

Y by

Lopes wrote:

Find all triplets of positive integers $(a,m,n)$ such that $a^m + 1 \mid (a + 1)^n$ .

If $a=1\Rightarrow (a,m,n)=(1,m,n)$ is a solution
If $a>1:$
If $m=1 \Rightarrow (a,m,n)=(a,1,n)$ is a solution
If $m>1:$
By Zsigmondy's Theorem:
$\exists$ prime $p/ p|a^m+1, p\nmid a+1$
$\Rightarrow p|(a+1)^n \Rightarrow p|a+1 (\Rightarrow \Leftarrow)$
But there is an exception $(m=3, a=2)$ :
$\Rightarrow 9|3^n \Rightarrow n>1$
$\Rightarrow (a,m,n)=(2,3,n), \forall n>1$ is a solution
$\Rightarrow (a,m,n)=(1,m,n),(a,1,n), ((2,3,n),\forall n>1)$ are all solutions

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

17 posts

AleMM

#29 h Jul 11, 2023, 4:54 AM

Y by

Hello again! :welcomeani:

:welcomeani:

I know this is a direct application of Zsigmondy's theorem (with base cases exception, of course), but I'd like to present other (instructive) solution.
Any flaws or misstypes that you find you can tell me, I'd like to know. Any kind of constructive feedback is welcomed!

Solution:

Let $a \sim b$ denote that $a$ has the same prime divisors as $b$ and vice versa, that's the same as saying that for a prime $p$ , $p|a \iff p|b$ .

Lemma: $\boxed{a^m+1 \sim a+1}$
First note that if $a^m+1 \sim a+1$ , then writing $a+1=p_1^{\alpha_1} \dots p_k^{\alpha_k}$ and $a^m+1=p_1^{\beta_1} \dots p_k^{\beta_k}$ we just take $n \geq \dfrac{\beta_i}{\alpha_i} \implies \alpha_i n \geq \beta_i \implies a^m+1|(a+1)^n$ (because every prime power in $(a+1)^n$ that is $\alpha_i n$ would be greater than $\beta_i$ due to how we defined $n$ ), so if $(a, m)$ satisfy $a^m+1 \sim a+1$ it tells us there are infinitely many suffuciently large $n$ for which $a^m+1|(a+1)^n$ . So in fact $(a, m)$ such that $a^m+1 \sim a+1$ give us solutions, we just need to prove that all $(a,m)$ solutions are of that form. Let $p$ be any prime divisor of $a^m+1 \implies p|a^m+1|(a+1)^n \implies p|(a+1)^n \implies p|a+1$ , so all prime divisors of $a^m+1$ appear in $a+1$ as well. Suppose $m$ is even, write it as $m=2m_0$ and take a prime divisor $p$ of $a^{2m_0}+1 \implies p|a^{2m_0}+1|(a+1)^n \implies p|a+1 \implies a \equiv -1 \pmod{p} \implies a^{2m_0} \equiv (-1)^{2m_0} \equiv -1 \pmod{p}$ , but $(-1)^{2m_0}=1 \implies 1 \equiv -1 \pmod{p} \implies p|1-(-1)=2 \implies p=2$ . It means that every prime divisor of $a^{2m_0}+1$ is 2, so it's a power of 2 $\implies a^{2m_0}+1 = 2^k$ for some $k \geq 1$ . If $k = 1 \implies a=1$ and in fact $\boxed{(1,m,n)}$ works for all positive integers $m,n$ . Now, suppose $k \geq 2 \implies 4|2^k \implies 4|a^{2m_0}+1 \implies (a^{m_0})^2 \equiv -1 \pmod{4}$ , but -1 isn't a quadratic residue modulo 4! So $m$ is odd $\implies a^m+1=(a+1)(a^{m-1}-a^{m-2}+ \dots -a+1) \implies a+1|a^m+1$ , so every prime divisor of $a+1$ must be a prime divisor of $a^m+1$ as well $\square$

Suppose $m > 1$ because $\boxed{(a,1,n)}$ works for $a,n$ positive integers. As we have $a^m+1 \sim a+1$ , that is $p|a^m+1 \iff p|a+1$ , but $p|a+1 \implies p|a^m+1$ , so we will only use that $p|a^m+1 \implies p|a+1$ . Choose $p$ to be a prime divisor of $(a^{m-1}-a^{m-2}+ \dots -a+1)$ , but because $a^m+1=(a+1)(a^{m-1}-a^{m-2}+ \dots -a+1) \implies p|a^m+1 \implies p|a+1 \implies a \equiv -1 \pmod{p}$ $\implies$ $a^{m-1}-a^{m-2}+ \dots -a+1 \equiv (-1)^{m-1}-(-1)^{m-2}+ \dots -(-1)+1 \equiv \underbrace{1+1+ \dots +1+1}_{m \text{ times}} \pmod{p}$ because $m$ is odd so $m-1$ is even and $m-2$ is odd... But $a^m+1 \equiv 0 \pmod{p} \implies m \equiv 0 \pmod{p}$ for all prime divisors $p$ of $(a^{m-1}-a^{m-2}+ \dots -a+1)$ . Which means that $p|(a^{m-1}-a^{m-2}+ \dots -a+1) \implies p|m$ . But notice that $p|(a^{m-1}-a^{m-2}+ \dots -a+1) \implies p|a+1$ because $a^m+1 = (a+1)(a^{m-1}-a^{m-2}+ \dots -a+1) \sim a+1$ , so by the LTE lemma we have that $V_p(a^{m-1}-a^{m-2}+ \dots -a+1)=V_p(\dfrac{a^m+1}{a+1})=(V_p(a+1)+V_p(m))-V_p(a+1)=V_p(m)$ because $p|a+1$ , so every prime divisor $p$ of $(a^{m-1}-a^{m-2}+ \dots -a+1)=\dfrac{a^m+1}{a+1}$ is in $m$ and $V_p(\dfrac{a^m+1}{a+1})=V_p(m)$ , thus $\dfrac{a^m+1}{a+1}|m$ .

Now we just do case work because $\dfrac{a^m+1}{a+1}|m \implies \dfrac{a^m+1}{a+1} \leq m$ and $\dfrac{a^m+1}{a+1}=(a^{m-1}-a^{m-2}+ \dots -a+1)$ is growing as $a$ grows, so $\dfrac{a^m+1}{a+1} \geq \dfrac{2^m+1}{3} \implies 3m-1 \geq 2^m$ , but $2^m > 3m-1$ for $m \geq 4$ and $m$ is odd, so $m=3$ ( $m=1$ already seen) $\implies n \geq 2$ and in fact $\boxed{(2,3,n)}$ works for all integers $n \geq 2$ . If $a=3 \implies 4m-1 \geq 3^m$ but for $m \geq 2$ we have that $3^m > 4m-1$ and if $a \geq 4$ we get $m \leq 1$ , finishing cases.

This post has been edited 2 times. Last edited by AleMM, Jul 11, 2023, 6:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

462 posts

#30 h Aug 9, 2023, 11:43 AM

Y by

Yeah sure, I agree Zsigmondy is good. But you know what's better? Mihăilescu's Theorem and bit of divisibility! The thing is, I was stuck on the last diophantine, but then someone told me this overkill theorem...

Solution: The answers are

$(a,m,n) = (1,m,n)$ ;
$(a,m,n) = (a,1,n), (2,3,n)$ for any positive integer $n$ .

We will begin by showing that even values of $m$ mostly don't work.

Claim: For even $m$ , the only solution is $(a,m,n) = (1,m,n)$ for any $m,n$ .

Proof: Let $p$ be some prime divisor of $a^m+1$ . Trivially, we get that $p \mid a + 1$ . For an even $m$ , this would imply that $p \mid (-1)^2 + 1 = 2$ . Altogether, one gets that $a+1$ is a power of $2$ and so must be $a^m + 1$ .

Write $a = 2^{\alpha} - 1$ for $\alpha \in \mathbb{Z}^+$ . Then we have that
$a^m + 1 = (2^\alpha - 1)^m + 1 = 2^\beta$ with $\beta \in \mathbb{Z}^+$ and $\beta > \alpha$ . Reducing the above equation modulo $2^\alpha$ , we get $\alpha = 1 \implies a = 2$ . Plugging everything back one can see the claim holds true. $\square$

The rest of the solution will deal with the harder case when $m$ is an odd integer. For this, write $a = p^k\cdot l - 1$ for some positive integer $l$ such that $\nu_p(a+1) = k$ .

Plugging this into the original relation, one would get
$(p^kl - 1)^m + 1 \mid (p^kl)^n.$ By Lifting the Exponent Lemma, we can check that $(p^kl - 1)^m + 1$ always divide $p^k$ . Since $p \nmid l$ , we must have that that
$(p^kl - 1)^m + 1 \mid l^n.$ Invoking the Binomial Theorem on the LHS, we would get that
$l(z) + p^k \mid l^{n-1}$ for some some integer $z$ . If $l \ne 1$ or $n \ne 1$ , then pick some prime divisor $t$ of $l$ such that $t \mid lz + p^k$ . But it would be immediately a contradiction. This means either of $l$ or $n$ must be unity.

The case for $n = 1$ , can be easily checked out by hand. The final non-trivial case is for $l = 1$ . As $m = 1$ clearly works, assume $m > 1$ henceforth. and the rest is easy. For this see that there exists some positive integer $e$ such that
$(p^k-1)^m + 1 = p^e.$ You can immediately kill this with Mihăilescu's Theorem and suddenly, the solution is complete! $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1292 posts

#31 h Sep 2, 2023, 12:02 AM

Y by

Note that $(a,1,n)$ , $(1,m,n)$ and $(2,3,n)\forall n\ge2$ are solutions. We claim that these are the only solutions. Suppose $a,m>1.$ Then, $n=1$ clearly doesn't work so $n>1$ as well. Also remove case $(2,3,n).$

By Zsigmondy a prime dividing a^m+1 doesn't divide a+1 so it doesn't divide (a+1)^n. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

50 posts

KOMKZ

#32 h Nov 30, 2023, 3:11 AM • 1 Y

Y by Adil1

I will prove with another way lets take for some $m$ we have $a^m+1$ have all prime divisors $a+1$ and dont have another divisors so $a^m+1$ and $(a+1)^m$ have similar divisors and its will kill the problem by binomial theorem

This post has been edited 1 time. Last edited by KOMKZ, Nov 30, 2023, 3:11 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

204 posts

Eka01

#33 h Oct 20, 2024, 3:25 PM

Y by

Storage

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

126 posts

#34 h Oct 24, 2024, 3:10 PM

Y by

Storage: Trivial by zsigmondy

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

33 posts

#35 h Feb 25, 2025, 7:47 AM

Y by

$(a,1,n),(1,m,n)$ are trivial solutions. Suppose, $a,m>1$ then by Zsigmondy theorem there exist a prime $p$ such that $p \nmid a+1$ with the exception being $(a,m)=(2,3)$ which is another solution.

This post has been edited 1 time. Last edited by HasnatFarooq, Feb 25, 2025, 7:49 AM
Reason: .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

49 posts

ray66

#36 h Apr 24, 2025, 3:52 AM

Y by

Suppose that $a,m$ >1. Then there are no solutions because there exists a prime $p$ that divides $a^m+1$ but not $a+1$ by Zsigmondy. The exception is $(2,3)$ , and plugging this in gives $(2,3,n)$ as a solution. $a=1$ is also a solution, and $m=1$ is another. So the only solutions are $(1,m,n)$ , $(m,1,n)$ , and $(2,3,n)$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

578 posts

#37 h Apr 24, 2025, 4:00 AM

Y by

If $a>2, m > 1$ by Zsigmondy's there is no solution. If $a > 2, m=1$ clearly $n$ can take any value so $(a, 1, n)$ works. If $a=2,$ by Zsigmondy's $m=3$ and then $n \geq 2$ suffices. So $(2, 3, k)$ where $k \geq 2$ works. Finally if $a=1$ we clearly have $(1, m, n)$ so the solutions (which clearly work) are $(a, 1, n), (2, 3, k), (1, m, n)$ with $k \geq 2.$

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a