IMO ShortList 2002, number theory problem 6

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

w

13 users

TOPICS

No tags match your search

M

No tags match your search

M

IMO ShortList 2002, number theory problem 6

G H J

Reveal topic tags

Laurentiu Panaitopol

L

G H BBookmark kLocked kLocked NReply

Source: IMO ShortList 2002, number theory problem 6

The post below has been deleted. Click to close.

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

3647 posts

orl

#1 h Sep 28, 2004, 1:11 PM • 10 Y

Y by Davi-8191, JasperL, Adventure10, ImSh95, Mango247, bjump, Tastymooncake2, cubres, and 2 other users

Find all pairs of positive integers $m,n\geq3$ for which there exist infinitely many positive integers $a$ such that $\frac{a^m+a-1}{a^n+a^2-1}$ is itself an integer.

Laurentiu Panaitopol, Romania

Attachments:

This post has been edited 6 times. Last edited by orl, Sep 27, 2005, 4:59 PM

Z K Y

The post below has been deleted. Click to close.

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

3647 posts

orl

#2 h Sep 28, 2004, 1:12 PM • 4 Y

Y by Adventure10, ImSh95, Mango247, cubres

Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

Z K Y

The post below has been deleted. Click to close.

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

64 posts

#3 h Dec 3, 2006, 9:39 PM • 4 Y

Y by ImSh95, Adventure10, Mango247, cubres

Ljunggren's theorem kills it.

//my bad, there is answer m=5, n=3.

Z K Y

The post below has been deleted. Click to close.

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

667 posts

#4 h Dec 4, 2006, 8:50 AM • 4 Y

Y by Adventure10, ImSh95, Mango247, cubres

May I know that what is"Ljunggren's theorem"?
Thanks.

Z K Y

The post below has been deleted. Click to close.

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

64 posts

#5 h Dec 4, 2006, 2:39 PM • 4 Y

Y by Adventure10, ImSh95, Mango247, cubres

http://www.math.sc.edu/~filaseta/seminars/MSRI2002/MSRILecture42002.pdf

Z K Y

The post below has been deleted. Click to close.

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

9 posts

hmm

#6 h Feb 23, 2009, 2:52 AM • 20 Y

Y by Amir Hossein, JasperL, Pure_IQ, ValidName, Kobayashi, jeteagle, megarnie, ImSh95, Adventure10, Mango247, Stuffybear, cubres, and 8 other users

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

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

2043 posts

Zhero

#7 h Mar 28, 2010, 9:02 PM • 6 Y

Y by Pure_IQ, ImSh95, Adventure10, Mango247, Stuffybear, cubres

hmm wrote:

Click to reveal hidden text

Wow, that was quite ingenious.

I have another finish to this problem which I feel is slightly cleaner:

Since $a^n + a^2 - 1 | a^m + a - 1$ , $a^n + a^2 - 1 | (a+1)(a^m + a - 1) - (a^n + a^2 - 1) = (a^{m+1} + a^m) + (a^2 - 1) - (a^n + a^2 - 1) = a^{m+1} + a^m - a^n = a^n(a^{m-n+1} + a^{m-n} - 1)$ . Therefore, $a^{n} + a^2 - 1 | a^{m-n+1} + a^{m-n} - 1$ . Hence, $n \leq m - n + 1$ , so $2n - 1 \leq m$ . But it was have shown that $m \leq 2n - 1$ , so we have that $m = 2n - 1$ . Therefore, $a^n + a^2 - 1 | a^n + a^{n-1} - 1$ , so $a^n + a^2 - 1 | a^{n-1} - a^2$ . The only way this can be is if $a^{n-1} = a^2$ , yielding $n = 3$ and $m = 5$ , as desired.

Z K Y

The post below has been deleted. Click to close.

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

606 posts

#8 h Sep 1, 2013, 11:26 PM • 7 Y

Y by JasperL, ValidName, ImSh95, Adventure10, Mango247, cubres, and 1 other user

We first show that $f(a) = a^n+a^2-1$ has no double root. But it is easy to see that $\gcd(f(a), f'(a)) = \gcd(a^n+a^2-1, na^{n-1}+2a) = 1$ (not hard, I can show this more explicitly). Now let $r$ be a root of $f(a)$ . Then $r^m+r-1 = 0, r^n+r^2-1 = 0$ .

Rearranging the above equations gives $r^m = 1-r, r^n = (1-r)(1+r)$ . Dividing these equations and rearranging gives $r^{m-n+1}+r^{m-n}-1 = 0$ . But this holds for all roots $r$ , so we get that $f(a) \vert a^{k+1}+a^k-1$ , where $k = m-n$ . By a rather famous result, $X^n-X-1$ is irreducible for all $n$ , so if we reverse the coefficients, $X^n+X^{n-1}-1$ is also irreducible. Therefore, $f(a) = a^{k+1} + a^k - 1 \implies n = 3, k = 2, \implies m = 5, n = 3$ .

This article seems to contain the proof that $X^n-X-1$ is irreducible in the beginning and much more later.

Z K Y

The post below has been deleted. Click to close.

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

44 posts

Nanas

#9 h Dec 29, 2014, 4:05 PM • 3 Y

Y by ImSh95, Adventure10, cubres

My solution is written in the language of modules of polynomials, though the key ideas are nearly the same. It is less elegant than solutions above (As usual). It may appear lengthy but it is just direct computations ( I didn't omit any details, it is just the same as in my scratch paper)

Denote $f(a)=\frac{a^m+a-1}{a^n+a^2-1}$ . . We let $P_m(x)=x^m+x-1$ and $Q_n(x)=x^n+x^2-1$ , we have since both polynomials are monics, we can use Euclidean theorem for monic integer polynomials, to conclude that there is $S,R\in \mathbb{Z}[x]$ where $\deg R < n$ , such that $P_m(x)= Q_m(x) S(x) + R(x)$ , we have then $f(x) = \frac{x^m+x-1}{x^n+x^2-1} = \frac {P_m(x)}{Q_n(x)}= S(x) + \frac{R(x)}{Q_n(x)}$ If $R(x)$ is non-zero, We get the $\frac{R(x)}{Q_n(x)} \rightarrow 0$ , which imply that for all but finitely many integers $s$ , $|\frac{R(x)}{Q_n(x)}| <1$ . And as that term never achieves zero for large numbers, we can't have $f(a)$ integer for infinitely many $a$ 's. So we must have $Q_n | P_m$ in $\mathbb{Z}[x]$ . Easily one can see that we must have $m > n$ .

Now we prove that $Q_n | P_m$ iff $(m,n)=(5,3)$ . We do module arithmetic in the Euclidean domain $\mathbb{Q}[x]$ to prove that. Note that $(x,Q_n(x))=1$ and $(x-1,Q_n(x))=1$ in $\mathbb{Q}[x]$ , and hence $\begin{array}{lcl} x^m+x-1 & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^m+x-x^n-x^2 & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^{m-1}+1-x^{n-1}-x & \equiv & 0\pmod{x^n+x^2-1} \\ \iff x^{n-1}(x^{m-n} - 1) + (1-x) & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^{m-2} + \cdots + x^{n-1} -1 & \equiv &0 \pmod{x^n+x^2-1} \end{array}$
If we let $m=n+i$ we get
$\begin{align*} x^{m-2} + \cdots + x^{n-1} -1 &\equiv x^{n+i-2}+ \cdots + x^{n-1} + x^{i} + x^{i-1} + \cdots + x^2 -1 \\ &\equiv (x^{n+i-2}+ x^{i})+ (x^{n+i-3}+x^{i-1}) + \cdots + ( x^{n} + x^{2}) + x^{n-1} - x^{i} - x^{i-1} - \cdots - x^{2} -1 \\ &\equiv x^{i-2}+ x^{i-3}+ \cdots +1 + x^{n-1} - x^{i} - x^{i-1} - \cdots - x^{2} -1 \\ &\equiv x^{n-1} + x - x^{i} - x^{i-1} \pmod{x^n+x^2-1} \end{align*}$
Now if $i<n$ we get $x^{n-1} + x - x^{i} - x^{i-1} = 0$ which cannot happen unless $n-1=i$ and $i-1=1$ and hence $(n,i)=(3,2)$ and so we have the solution $(m,n) = (5,3)$ . Now if $i=n+j ; j\geq0$ , then $\begin{array}{lcl} x^{n-1} + x - x^{i} - x^{i-1} & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff - x^{n-1} - x + x^{n+j} + x^{n+j-1} & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^{n+j-1} + x^{n+j-2} - x^{n-2} - 1 & \equiv & 0\pmod{x^n+x^2-1} \\ \iff x^{n-2}(x^{j+1}-1) + x^{n+j-2} - 1 & \equiv & 0 \pmod{x^n+x^2-1} \\ \iff x^{n+j-2} + 2x^{n+j-3} + \cdots + 2x^{n-2}+ x^{n} + \cdots + 1 & \equiv &0 \pmod{x^n+x^2-1} \end{array}$

But $x^{n+j-2} + 2x^{n+j-3} + \cdots + 2x^{n-2}+ x^{n} + \cdots + 1 \geq 1$ for $x\geq0$ , while $s^n+s^2-1=0$ for some $s\in(0,1)$ since divisibility applies also in $\mathbb{R}[x]$ , we get $s^{n+j-2} + 2s^{n+j-3} + \cdots + 2s^{n-2}+ s^{n} + \cdots + 1 = 0$ , getting a contradiction.

This post has been edited 2 times. Last edited by Nanas, Aug 4, 2015, 6:17 PM

Z K Y

The post below has been deleted. Click to close.

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

1963 posts

ABCDE

#11 h May 18, 2016, 6:51 PM • 5 Y

Y by randomusername, ImSh95, Adventure10, Mango247, cubres

I found a pretty cool and unique solution to this problem. Can someone check for its validity?

Solution

Z K Y

The post below has been deleted. Click to close.

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

641 posts

tree3

#12 h Jan 20, 2018, 1:32 AM • 4 Y

Y by ImSh95, Adventure10, Mango247, cubres

Notice that $m>n$ since $m,n>3$ implies that if $m \leq n$ , then $0<\frac{a^m+a-1}{a^n+a^2-1}<1$ for $a$ relatively large. First we claim that $\frac{a^m+a-1}{a^n+a^2-1}$ must always be an integer. Indeed, since $\frac{a^m+a-1}{a^n+a^2-1}=R(x)+\frac{Q(x)}{a^n+a^2-1}$ for polynomials $R,Q$ , with $deg(Q)<deg(a^n+a^2+1)$ , implying that for large $a$ , $Q(x)<a^n+a^2-1$ occurs, meaning that the quotient cannot yield an integer unless $Q(x)=0$ for infinitely many values, implying the above claim. Now we can bound. Since
$a^n + a^2 - 1 | a^m + a - 1$ , we get that $a^n + a^2 - 1 | (a+1)(a^m + a - 1) - (a^n + a^2 - 1)$ .
But $(a+1)(a^m + a - 1) - (a^n + a^2 - 1)= a^{m+1} + a^m - a^n = a^n(a^{m-n+1} + a^{m-n} - 1)$ .
Therefore, $a^{n} + a^2 - 1 | a^{m-n+1} + a^{m-n} - 1$ . Hence, $n \leq m - n + 1$ , so $2n - 1 \leq m$ . Plugging in $a=2$ , we immediately get $2^n+3|2^m+1$ with $m<2n$ . Then $gcd(2^n+3,2^m+1)=gcd(3(2^{m-n})-1,2^n+3)$ . Since $3(2^{m-n})-1<3(2^{m-n})<3(2^n)$ and $3(2^{m-n})-1$ is odd, $3(2^{m-n})-1=2^n+3$ . This rearranges to $3(2^k)=2^n+4$ for $k=m-n$ . Since $n>2$ , $k<2$ , implying the only solution to be $m=5,n=3$ .

This post has been edited 6 times. Last edited by tree3, Jan 20, 2018, 1:37 AM

Z K Y

The post below has been deleted. Click to close.

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

6877 posts

#13 h Apr 8, 2019, 1:32 PM • 4 Y

Y by v4913, ImSh95, Adventure10, Mango247

The condition is equivalent to $a^n+a^2-1$ dividing $a^m+a-1$ as polynomials. The big step is the following analytic one.

Claim: We must have $m \le 2n$ .

Proof. Assume on contrary $m > 2n$ and let $0 < r < 1$ be the unique real number with $r^n+r^2 = 1$ , hence $r^m+r = 1$ . But now $\begin{align*} 0 &= r^m + r - 1 < r(r^n)^2 + r - 1 = r\left( (1-r^2)^2+1 \right) - 1 \\ &= -(1-r)\left( r^4+r^3-r^2-r+1 \right). \end{align*}$ As $1-r > 0$ and $r^4+r^3-r^2-r+1 > 0$ , this is a contradiction $\blacksquare$

Now for the algebraic part. Obviously $m > n$ . $\begin{align*} a^n+a^2-1 &\mid a^m+a-1 \\ \iff a^n+a^2-1 &\mid (a^m+a-1)(a+1) = a^m(a+1) + (a^2-1) \\ \iff a^n+a^2-1 &\mid a^m(a+1) - a^n \\ \iff a^n+a^2-1 &\mid a^{m-n}(a+1) - 1. \end{align*}$ The right-hand side has degree $m-n+1 \le n+1$ , and the leading coefficients are both $+1$ . So the only possible situations are $\begin{align*} a^{m-n}(a+1) - 1 &= (a+1)\left( a^n+a^2-1 \right) \\ a^{m-n}(a+1) + 1 &= a^n+a^2-1. \end{align*}$ The former fails by just taking $a=-1$ ; the latter implies $(m,n) = (5,3)$ . As our work was reversible, this also implies $(m,n) = (5,3)$ works, done.

This post has been edited 1 time. Last edited by v_Enhance, Apr 8, 2019, 5:10 PM

Z K Y

The post below has been deleted. Click to close.

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

1980 posts

#14 h May 19, 2019, 7:01 PM • 5 Y

Y by ELMOliveslong, SatisfiedMagma, ImSh95, Adventure10, Mango247

orl wrote:

Find all pairs of positive integers $m,n\geq3$ for which there exist infinitely many positive integers $a$ such that $\frac{a^m+a-1}{a^n+a^2-1}$ is itself an integer.

Laurentiu Panaitopol, Romania

It is standard to prove that $x^n+x^2-1 \mid x^m+x-1$ as polynomials, by the given condition. Now the former has different signs at $x=0$ and $x=1$ , so pick a root $0<\alpha<1$ . Notice that $\alpha^n+\alpha^2=1$ and $\alpha^m+\alpha=1$ . Suppose $m \ge 2n$ . Then $\alpha^m \le \alpha^{2n} \implies 1=\alpha^2+\alpha^n<\alpha+\alpha^{2n} \iff \alpha^{2n}-\alpha^2>\alpha^n-\alpha \iff \alpha^n+\alpha<1=\alpha^2+\alpha^n \iff \alpha<\alpha^2 \iff \alpha>1$ which is a contradiction!

So $m<2n$ . Now $x^n+x^2-1 \mid x^{m-n+1}+x^{m-n}-1$ by taking residues. Finally, the latter polynomial has degree $m-n+1 \le (2n-1)-(n-1)$ so in fact, these two polynomials are equal, hence $m-n=2, m=2n-1$ so $m=5, n=3$ . Clearly, this pair works, so 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.

691 posts

#15 h Apr 2, 2020, 8:36 AM • 1 Y

Y by ImSh95

Kind of nice.
The condition forces the polynomial $a^n + a^2 - 1$ to divide $a^m + a - 1$ .
$\textbf{Claim 01.}$ $m < 2n$ .
$\textit{Proof.}$ Suppose otherwise, we have $m \ge 2n$ .
Notice that $(0)^n + (0)^2 - 1 = -1$ and $(1)^n + (1)^2 - 1 = 1$ . By the Intermediate Value Theorem, we have that the polynomial $a^n + a^2 - 1$ has a root $\alpha$ which satisfy $0 < \alpha < 1$ . Therefore,
$\alpha^m + \alpha = \alpha^n + \alpha^2 \Rightarrow \alpha (1 - \alpha) = \alpha^n (1 - \alpha^{m - n}) = (1 - \alpha^2)(1 - \alpha^{m - n})$ This gives us
$\alpha = (1 + \alpha)(1 - \alpha^{m - n})$ which can be rewritten as $\alpha^{m - n} + \alpha^{m - n + 1} = 1$ . Since $m - n + 1 > n \ge 3$ and $0 < \alpha < 1$ . We have
$1 = \alpha^{m - n} + \alpha^{m - n + 1} \le \alpha^n + \alpha^{n - 1} \le \alpha^n + \alpha^2= 1$ results to a clear contradiction.

Now, we have
$x^n + x^2 - 1 | x^{m - n + 2} - x^{m - n} - x + 1$ Notice that we have the bound $n \le m - n + 2 \le n + 1$ .
We'll prove that we must have $m - n + 2 = n + 1$ .
Assume otherwise, then we must have $LHS = RHS$ since they are both the polynomial in the same degree and both having leading coefficient $1$ , which is a clear contradiction as $RHS$ has constant $+1$ and $LHS$ has constant $-1$ .
Then we have $m - n + 2 = n + 1$ .
By considering the constant term ad the largest coefficient, we deduce
$(x^n + x^2 - 1)(x - 1) = x^{n + 1} - x^{n - 1} - x + 1$ But taking $x = 2$ . We have $LHS = 2^n + 2^2 - 1 \le 2^{n} + 2^{n - 1} - 1$ since $n \ge 3$ .
For equality to hold, we must have $n = 3$ . This forces $m = 5$ , and we could check that
$(x^3 + x^2 - 1)(x^2 - x + 1) = x^5 + x - 1$ Therefore, the pair $(3,5)$ clearly satisfies.

Z K Y

The post below has been deleted. Click to close.

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

15 posts

#16 h Apr 2, 2020, 12:17 PM • 4 Y

Y by thczarif, AlastorMoody, yayitsme, ImSh95

Lemma: For $a, m, n\in \mathbb{N}$ , we have
$a^n+a^2-1\ |\ a^{m-i} + (-1)^i\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^i\left(a-1\right)$
Proof: We proceed by induction on $i$ . For $i=0, 1$ , it is true. So assume for some $i>2$ , it is true.

$\begin{align*} a^n+a^2-1\ &|\ a^{m-i} + (-1)^i\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^i\left(a-1\right)\\[1em] \implies a^n+a^2-1\ &|\ a^{m-i} + (-1)^i\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^i\left(a-1\right) - (-1)^i(a^n+a^2-1)\\[.5em] &=a^{m-i} + (-1)^i\left(-a^n+ a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^{i+1}(a^2-a)\\[1em] \therefore a^n+a^2-1\ &|\ a^{m-i-1} + (-1)^{i+1}\left(a^{n-1} - a^{n-2} +\dots + (-1)^{i+1}a^{n-i}\right) + (-1)^{i+1}\left(a-1\right)\\ \end{align*}$ Which proves our lemma.

Now, let $i=n$ , we get,
$a^n+a^2-1\ |\ a^{m-n} + (-1)^n \left(\frac{a^n+1}{a+1}\right) + (-1)^n(a-1)$ Clearly, $m\ge n$ . Let $m=nk+q$ . If $n$ is even,
$\begin{align*} a^n+a^2-1\ &|\ a^{m-n}+a-1 + \left(\frac{a^n+1}{a+1}\right)\\[.5em] \implies a^n+a^2-1\ &|\ a^q+a-1 + k\left(\frac{a^n+1}{a+1}\right) \end{align*}$
Which is not possible since the polynomial on the right side has degree at most $n-1$ , and can't be $0$ for all $a\in \mathbb{Z}$ .

So, $n$ is odd. Then we have,

$\begin{align*} a^n+a^2-1\ &|\ a^{m-n} + a-1 - \left(\frac{a^n+1}{a+1}\right) - 2(a-1)\\[.5em] \implies a^n+a^2-1\ &|\ a^q + a -1 - k\left(\frac{a^n+1}{a+1}\right) -2k(a-1) = P(a) \end{align*}$
Since $P(a)$ has degree at most $n-1$ , $P(a) =0$ for all $a\in \mathbb{Z}$ .

$\begin{align*} P(a) &= a^q + a -1 - k\left(\frac{a^n+1}{a+1}\right) -2k(a-1)\\ \therefore a^q + a - 1 &= k\left(\frac{a^n+1}{a+1}\right)+2k(a-1) \end{align*}$
Comparing the coefficients and degrees on both sides, we have, $q=n-1=2,\ k=1$ . Which gives us the only solution $(m, n) = (5, 3)$ .

Z K Y

The post below has been deleted. Click to close.

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

558 posts

#17 h Jun 26, 2020, 7:45 AM • 4 Y

Y by AlastorMoody, parola, ImSh95, Mango247

The problem is a joke if someone knows a particular lemma.

Here's my solution

This post has been edited 2 times. Last edited by Aryan-23, Jun 26, 2020, 7:51 AM
Reason: YUHHHHHHHH

Z K Y

The post below has been deleted. Click to close.

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

dchenmathcounts

2443 posts

dchenmathcounts

#18 h Oct 11, 2020, 4:28 AM • 1 Y

Y by ImSh95

Cool problem!

We require $a^n+a^2-1\mid a^m+a-1$ , else the remainder (which is deg $n-1$ at most) will eventually be smaller than $a^n+a^2-1$ for large enough $a.$

Also note $n<2m$ otherwise $a^m+a>a^{2m}+a^2>a^n+a^2$ for $0<a<1$ and obviously one of the roots has this value. So then the remainder is $-a^{m-n+2}+a^{m-n}+a-1,$ so we want $a^n+a^2-1\mid a^{m-n+2}-a^{m-n}-a+1,$ which must be equal to $a^n+a^2-1$ or $(a^n+a^2-1)(a-1)$ as $m-n+2\leq m+1.$ For size reasons $m-n+2=m$ or $m-n+2=m+1$ . The first case fails by comparison of $a$ coefficient, and the second case requires $n=3$ , which gives us $(a^3+a^2-1)(a-1)=a^m+a-1,$ fixing $m=5.$

So just $(3,5)$ works.

Z K Y

The post below has been deleted. Click to close.

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

DottedCaculator

7348 posts

DottedCaculator

#19 h Nov 8, 2021, 2:29 AM • 2 Y

Y by megarnie, ImSh95

Solution

Z K Y

The post below has been deleted. Click to close.

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

1350 posts

i3435

#20 h Dec 11, 2022, 12:48 PM • 4 Y

Y by ImSh95, Mango247, Mango247, Mango247

Here is a weird reason why $m<2n$ which I can't find above, given that we already know $x^n+x^2-1$ has to divide $x^{m-n+1}+x^{m-n}-1$ .

Both of these polynomials are monotonic when $x>0$ , and one divides the other, so it is impossible for them to have different signs for some $x>0$ . Consider $x=\frac{1}{2}^{\frac{1}{n}}$ . $\left(\frac{1}{2}^{\frac{1}{n}}\right)^n+\left(\frac{1}{2}^{\frac{1}{n}}\right)^2-1=\frac{1}{2}+\frac{1}{2}^{\frac{2}{n}}-1>0$ since $\frac{2}{n}<1$ . On the other hand, $\left(\frac{1}{2}^{\frac{1}{n}}\right)^{m-n+1}+\left(\frac{1}{2}^{\frac{1}{n}}\right)^{m-n}-1=\left(\frac{1}{2}^{\frac{1}{n}}+1\right)\left(\frac{1}{2}^{\frac{m-n}{n}}\right)-1$ . The first part of the product is $<2$ and since $\frac{m-n}{n}\ge 1$ , the second part of the product is $\le \frac{1}{2}$ . Thus this is $<0$ , giving the desired contradiction.

Z K Y

The post below has been deleted. Click to close.

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

1523 posts

#21 h Dec 21, 2022, 3:20 AM • 1 Y

Y by ImSh95

Let $f(x)=x^n+x^2-1$ and $g(x)=x^m+x-1$ be polynomials in $\mathbb Z[x]$ . We claim that $(m,n)=(5,3)$ works.
Claim 1: $f \mid g$ holds always.
Proof: For any $x \in \mathbb C$ we do polynomial division with quotient and residue in $\mathbb Z[x]$
$g(x)=f(x)q(x)+r(x) \implies \frac{g(x)}{f(x)}=q(x)+\frac{r(x)}{f(x)}$ From here note that $\text{deg} \; r<\text{deg} \; f$ so set $x$ to be a extremely large positive integer such that $-f(x)<r(x)<f(x)$ meaning that for infinite values $r$ is 0 so $r(x)=0$ holds always meaning that $f \mid g$ as desired.
Claim 2: $2n-1 \ge m$
Proof: From Claim 1 one has that all the roots of $f$ are also roots of $g$ now $f'(x)=nx^{n-1}+2x>0$ if $x>0$ hence $f$ is strictly increasing in $\mathbb R^+$ , now $f(1)=1$ and $f\left(\frac{2}{3} \right)=\left(\frac{2}{3} \right)^n-\frac{5}{9}<0$ meaning that there exists a root of $f$ satisfying $\frac{2}{3}<z<1$ .
Assume FTSOC that $m \ge 2n$ then by all said before and ineqs
$(1-z^2)^2=z^{2n}\ge z^m=1-z \implies (1-z)(z^2+z+1+z) \ge 1 \implies 1-z^3+z-z^2 \ge 1 \implies 1 \ge z+z^2 \ge 3z-1 \implies \frac{2}{3} \ge z \; \text{contradicction!!}$ Contradiction comes from assuming $m \ge 2n$ hence $2n-1 \ge m$ as desired.
A nice finish: Lets now work in integers and divisions
$a^n+a^2-1 \mid a^m+a-1 \implies a^n+a^2-1 \mid a^{m-n+2}-a^{m-n}+1-a=(a-1)(a^{m-n}(a+1)-1) \implies a^n+a^2-1 \mid a^{m-n}(a+1)-1$ From here as RHS has at most degree $n$ we see that both have to be equal and $m=2n-1$ hence $a^n+a^2-1=a^n+a^{n-1}-1$ which means $n=3$ and this means $m=5$ .
Hence the pair $(m,n)=(5,3)$ is the unique pair that works, thus we are done

Z K Y

The post below has been deleted. Click to close.

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

458 posts

#22 h Jun 30, 2023, 6:12 PM • 1 Y

Y by ImSh95

Did it back like 2 years ago? Very cool problem. Solved with quirtt and Fafnir.

Solution: We will show that $(m,n)=(5,3)$ is the only solution. One can see that it works as
$a^5+a-1=(a^2-a+1)(a^3+a^2-1).$ We will break the solution into two claims which will bound the values of $m$ . We define $\begin{align*} P(a) \overset{\text{def}}{=} a^m+a-1 \\ Q(a) \overset{\text{def}}{=} a^n+a^2-1 \end{align*}$ where $P,Q$ are polynomials. We will now prove a well-known but extremely useful lemma which will take the problem from Number Theory to Algebra!

Lemma: If two polynomials $f,g \in \mathbb{Z}[x]$ are such that $f(n) \mid g(n)$ for infinitely many integers $n$ , then $f(x) \mid g(x)$ .

Proof: Due to size reasons, it is easy to see $\deg(g) > \deg(f)$ . By the division algorithm over $\mathbb{Q}[x]$ , write $g = fq + r$ for $f,q \in \mathbb{Q}[x]$ and $\deg(r) < \deg(f)$ . One can clear out the denominators by multiplying by suitable integer, so we assume that all the polynomials are in $\mathbb{Z}[x]$ . Just pick huge $k$ such that $f(k) \mid g(k)$ . It would actually mean that $f(k) \mid r(k)$ . But since $\deg(r) < \deg(f)$ , we must have $r \equiv 0$ as desired. $\square$

So, we can actually apply the lemma to reduce the problem down to just two polynomials dividing each other!

Claim: $2n-1 \le m$ .

Proof: First of all notice that $\gcd(a+1,Q(a))=1$ . The algebra for divisibility begins here $\begin{align*} P(a) & \equiv 0 \pmod{Q(a)} \\ (a+1)P(a) & \equiv 0 \pmod{Q(a)} \\ a^{m+1}+a^2-a+ a^m+a-1 & \equiv 0 \pmod{Q(a)} \\ a^{m+1}+a^m+a^2-1 & \equiv 0 \pmod{Q(a)} \\ a^{m+1}+a^m-a^n & \equiv 0 \pmod{Q(a)} \\ a^{m-n+1}+a^{m-n}-1 & \equiv 0 \pmod{Q(a)} \\ \end{align*}$ Bringing this into divisibility condition, we get $\begin{align} a^n+a^2-1 \mid a^{m-n+1}+a^{m-n}-1 \label{1} \end{align}$ Due the bound on the degree, we get $m-n+1 \ge n$ which on simplifying gives $2n-1 \le m$ as desired. $\square$

The next is claim is a little harder to come up with and prove.

Claim: $m < 2n$ .

Proof: Assume for the sake of contradiction, that $m>2n$ . By the Intermediate Value Theorem, there exists a real root of $Q$ which lies between 0 and 1. Let this root be $\alpha$ . By the problem condition, $\alpha$ is also a root of $P$ . Now $P(\alpha)$ and $Q(\alpha)$ gives the following $\begin{align} \alpha^m + \alpha = 1 \\ \alpha^n + \alpha^2 = 1 \end{align}$ Now we compute $\alpha^m$ and $\alpha^{2n}$ . $\begin{align*} \alpha^m & = 1- \alpha \\ \alpha^{2n} & = (1-\alpha^2)^2 \\ \end{align*}$ By assumption, we must have $\alpha^m < \alpha^{2n}$ . Plugging in the values, we get $\begin{align*} 1-\alpha & \le (1-\alpha^2)^2 \\ 1-\alpha & \le (1-\alpha)^2(1+\alpha)^2 \\ 1 & \le (1-\alpha)(1+\alpha)^2 \\ \iff \alpha & \le \varphi \end{align*}$ where $\varphi$ is the golden ratio. We will now show that $\alpha > \varphi$ which would bring the desired contradiction. It is easy to see that $P$ is an increasing function in the interval $[0,1]$ . Note that $\begin{align*} P(\varphi)=\varphi^m+\varphi-1 & < \varphi^2+\varphi-1 = 0 = P(\alpha) \\ \implies P(\varphi) & < P(\alpha) \end{align*}$ and we can conclude that $\alpha > \varphi$ and we are done with the claim. $\square$

Now, due to the bounds we just need to check the case for $m=2n-1$ . Putting this in $(1)$ we get
$a^n+a^2-1 \mid a^{n-1}-a^2.$ This forces $n=3$ and we are done. $\blacksquare$

This post has been edited 2 times. Last edited by SatisfiedMagma, Jun 30, 2023, 6:27 PM
Reason: ayooo meth

Z K Y

The post below has been deleted. Click to close.

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

1292 posts

#23 h Sep 4, 2023, 7:16 PM

Y by

solved with hint to consider r, otherwise im very proud of myself

It's obvious that m>n; we want to find m,n s.t. $a^{m-n+2}-a^{m-n}-a+1\equiv a^m+a-1-a^{m-n}(a^n+a^2-1)\equiv0\pmod{a^n+a^2-1}$ .
We claim that $m\le 2n$ .
Assume FTSOC m>2n, and take 0<r<1 as the real number root of both polynomials. We have $0=r^m+r-1\le r^{2n+1}+r-1=-(1-r)(r^4+r^3-r^2-r+1),r^4+r^3-r^2-r+1>r^2(r^2+r-1)>r^2(r^m+r-1)=0,1-r>0\implies 0\le RHS<0,$ impossible.

Case 1. m=2n. We have $a(a^3-2a+1)\equiv a^{n+2}-a^n-a+1-(a^2-1)(a^n+a^2-1)\equiv0\pmod{a^n+a^2-1}\implies n=\{1,2,3\}$ , none of which work.
Case 2. m=2n-1. We have $a^{n-1}+a^3-1\equiv a^{n+1}-a^{n-1}-a+1-a(a^n+a^2-1)\equiv0\pmod{a^n+a^2-1}$ , and checking the possible n, only $\boxed{n=3,m=5}$ works.
Case 3. m=2n-2 has similar computation with degrees on n, and none of n work. Case 4 has $m\le 2n-3$ , none of which work by looking at deg LHS<deg RHS except for a few n, and checking those don't work. Having exhausted all cases, we conclude the proof here.

Remark. After enough of these problems, reducing the degree of polynomials by suitably subtracting multiples of the modulus becomes second nature; it's very natural to do so by euclidean algorithm, and once LHS|RHS with LHS deg<RHS deg except for a few numbers, the problem is solved.

This post has been edited 2 times. Last edited by huashiliao2020, Sep 4, 2023, 7:19 PM

Z K Y

The post below has been deleted. Click to close.

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

5001 posts

#24 h Oct 4, 2023, 1:13 PM

Y by

The answer is $(m,n)=(5,3)$ only, which clearly works since $a^3+a^2-1 \mid a^5+a-1$ in the polynomial sense. We now prove this is the only one.

For fixed $(m,n)$ , since $a^n+a^2-1$ is monic we can write
$\frac{a^m+a-1}{a^n+a^2-1}=p(a)+\frac{q(a)}{a^n+a^2-1}$ for some $p,q \in \mathbb{Z}[x]$ and $\deg q<n$ . Then by considering sufficiently large $a$ we require $q \equiv 0$ , so we should have $a^n+a^2-1 \mid a^m+a-1$ in the polynomial sense. Note that both of these polynomials have exactly one positive real root, so they must be the same. Call this common root $r$ ; clearly $r<1$ .

Claim: $m<2n$ .
Proof: Suppose otherwise. We should then have
$1=r^n+r^2=r^m+r<r^{2n}+r \implies r-r^2>r^n-r^{2mn}.$ On the other hand, since $r^m<r$ but $r^n=1-r^2>1-r$ , this is impossible, since $x-x^2$ increases as $x$ gets closer to $1/2$ . $\blacksquare$

Now let $m=n+k$ with $0 \leq k \leq n-1$ (since clearly $m \geq n$ ). We should have
$a^n+a^2-1 \mid a^k(a^n+a^2-1)-(a^{n+k}+a-1)=a^{k+2}-a^k-a+1=(a-1)(a^{k+1}+a^k-1).$ Since $\gcd(a^n+a^2-1,a-1)=1$ (in the polynomial sense) it follows that $a^n+a^2-1 \mid a^{k+1}+a^k-1$ . In general $a^{k+1}+a^k-1$ is a nonzero polynomial, so $k<n-1$ is impossible, hence $k=n-1$ and $a^n+a^2-1 \mid a^n+a^{n-1}-1 \implies a^n+a^2-1 \mid a^{n-1}-a^2$ . The last polynomial has degree less than $n$ , hence it must be zero, i.e. $n=3$ . Thus we extract the claimed solution. $\blacksquare$

Remark: Good problem to test "polynomial" intuition? To me considering $r$ felt "intuitive" but it's not super motivated in itself. I guess you start thinking about the roots after divisibility, and these are mostly hard to pin down except $r$ .

This post has been edited 1 time. Last edited by IAmTheHazard, Oct 4, 2023, 1:16 PM

Z K Y

The post below has been deleted. Click to close.

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

198 posts

#25 h Oct 5, 2023, 6:47 AM

Y by

The only answer is $(m, n) = (5, 3)$ .

Obviously $m > n$ . It's not hard to see that $x^n + x^2 - 1 \mid x^m + x - 1$ . Let $r$ be a real root of $x^n + x^2 - 1$ . Then $r$ is real root of $x^m + x - 1$ . Thus $r^n + r^2 = r^m + r$ , which is equivalent to $r(1 - r) = r^n(1 - r^{m-n})$ .

If $m > 2n$ , then $r(1 - r) = r^n(1 - r^{m-n}) > r^n(1 - r^{n}) \ge r(1 - r)$ , a contradiction. Thus $m \le 2n$ .

Now note that $x^n + x^2 - 1 \mid (x + 1)(x^m + x - 1) = x^{m+1} + x^m + x^2 - 1$ , thus $x^n + x^2 - 1 \mid x^{m-n}(x + 1) - 1$ . Since $m - n + 1 \le n + 1$ , thus $x^{m-n}(x + 1) - 1 = (x + 1)(x^n + x^2 - 1)$ or $x^{m-n}(x + 1) - 1 = x^n + x^2 - 1$ . In the first case we have $x^{n+1} + x^n + x^3 + x^2 - x - 1 = x^{n} + x^2 - 1$ , which is impossible. In the second case we have $x^n + x^2 - 1 = x^n + x^{n-1} - 1$ , thus $n = 3$ . Thus $m = 5$ . Therefore $(m, n) = (5, 3)$ is only answer. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

awesomeming327.

1712 posts

awesomeming327.

#26 h Nov 24, 2023, 4:15 AM

Y by

Note that these are both polynomials, so if for infinitely many $a$ , $a^n+a^2-1\mid a^m+a-1$ then the polynomial $a^n+a^2-1$ divides the polynomial $a^m+a-1$ . Note that $P(x) \mid Q(x)$ implies $\text{deg} P\le \text{deg} Q$ . In particular, $m\ge n$ .

Since $a^n + a^2 - 1\mid a^m+a-1$ , which implies $a^n+a^2-1|(a+1)(a^m+a-1)-(a^n+a^2-1)$ . This becomes $a^n+a^2-1\mid a^{m+1}+a^{m}-a^n$ . Note that $\gcd(a^n+a^2-1,a)=\gcd(a^2-1,a)=1$ so $a^n+a^2-1\mid a^{m-n+1}+a^{m-n}-1$ . This implies $m\ge 2n-1$ . This also means $m-n\ge n-1\ge 2$ .

By IVT and taking the derivative, there exists a unique real $0<r<1$ for which $r^n+r^2-1=0$ . We must have $r^m+r-1=0$ . Setting them equal, we get
$r=\frac{r^n(1-r^{m-n})}{1-r}=\frac{(1-r^2)(1-r^{m-n})}{1-r}=(1+r)(1-r^{m-n})$ and this becomes $r^{m-n}(r+1)=1=r^n+r^2\ge r^n+r^{m-n}$ which implies $r^{m-n+1}\ge r^n\implies m-n+1\le n$ so $m\le 2n-1$ . Note that equality is dependent on $m-n=2$ , so we need $(m,n)=(5,3)$ which works.

Z K Y

The post below has been deleted. Click to close.

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

8859 posts

#27 h Dec 16, 2023, 11:37 PM

Y by

Claim. [Main Claim] $m \leq 2n$ .

Proof. Let $r$ be a root of $a^n + a^2 - 1 = 0$ , such that $r^n + r^2 = r^m + r = 1$ . Suppose for the sake of contradiction that $m > 2n$ . Then,
$\begin{align*} r^m + r &< r^{2n} + r \\ &= (r^n - r^{n+2}) + r \\ &= 1 - 2r^2 + r^3 + r \\ 0 &< r^4 + r - 2r^2 \\ &=r(r-1)(r^2+r-1). \end{align*}$ On the other hand, $r^2 + r > 1$ and $r - 1 < 0$ , so this is a clear contradiction. $\blacksquare$

Now, by Euclidean algorithm we have $a^n + a^2 - 1 \mid (a-1)(a^{m-n+1}+a^{m-n} - 1).$ In particular, as $a^n + a^2 - 1 \equiv 1 \pmod {a-1}$ , we have $a^n + a^2 - 1 \mid a^{m-n+1} + a^{m-n} + 1.$ If $m \leq 2n-2$ , then the RHS is clearly smaller and $a^{m-n+1}+a^{m-n} + 1 = 0$ , which is clearly impossible.

If $m \in \{2n-1, 2n\}$ , perform one more step to get $a^n + a^2 - 1 \mid a^{m-n} + a^{m-2n+1}-a^{m+3-2n} - 1.$ As $m-2n+1 \leq 1$ , the RHS is smaller than the LHS now, so it must uniquely equal zero. When $m = 2n-1$ , we get $a^{n-1} = a^2$ , giving the solution pair $(3, 5)$ . When $m = 2n$ , we get $a^n + a - a^3 - 1=0$ , which does not work for any value of $n$ . Thus, $(3, 5)$ is the only solution.

This post has been edited 1 time. Last edited by HamstPan38825, Dec 16, 2023, 11:37 PM

Z K Y

The post below has been deleted. Click to close.

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

795 posts

#28 h Mar 30, 2024, 2:23 AM

Y by

We claim our only solution is $\boxed{(5,3)}$ . Our condition, $N/D \in \mathbb{Z}$ , can be rewritten as
$D \mid a^{m-n}\left(a^n+a^2-1\right) - \left(a^m+a-1\right) \implies D \mid a^{m-n+1}+a^{m-n}-1.$
There are clearly no solutions for $m \leq 2n-2$ , and investigating $m=2n-1,2n$ gives the desired solution. Now assume FTSOC $m>2n$ , and consider a root $0<r<1$ of $D \mid N$ . Then
$\left(a^n+a^2\right)^2 - (a^m+a) = 0 \implies a\left(2a^{n+1}+a^3-1\right) = a^m-a^{2n}.$
The RHS is negative under the assumption, but the LHS can be expressed as
$a\left((a^{n+1})+a(a^n+a^2)\right)-(a^n+a^2) = a(1-a)(a-a^n) > 0. \quad \blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

1015 posts

bjump

#29 h May 10, 2024, 11:56 PM • 1 Y

Y by megarnie

solution (arch carried me :skull:)

Z K Y

The post below has been deleted. Click to close.

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

186 posts

#30 h Jun 3, 2024, 11:53 AM

Y by

Let $P(a)$ be the enumerator and $Q(a)$ be the denominator. Divide $P$ on $Q$ :
$P=QT+R$ where $deg R<def Q$ and division is done in $\mathbb{Q}$ . Multiply this equation by the lcm of denominators so that all coeffiecients were integer. Now $Pc$ is divisible by $Q$ and $(Tc)Q$ are divisible by $Q$ in infinitely many points from the problem statement, thus $Rc$ is also divisible by $Q$ in infinitely many points. But if $R \neq 0$ , then eventually $|Rc| < |Q|$ , so $R$ must be equal to zero. Hence $P$ is divisible by $Q$
Now $a^{m+1}+a^{m}-a^n=(a+1)P-Q \vdots Q$ , but $(Q,a)=1$ , thus $a^{m-n+1}+a^{m-n}-1 \vdots Q$ . Denote $m-n=t$
Obviously $t+1 \geq$ deg $Q=n$ . Note that $Q(0)=-1$ and $Q(1)=1$ , thus there exists a number $x_0 \in (0,1)$ such that $Q(x_0)=0$ . Then $x_0^{t+1}+x_0^{t}=1=x_0^n+x_0^2$ . Note that if $t>2$ , then $x_0^{t+1} \leq x_0^n$ and $x_0^t<x_0^2$ , contradicting the statement. Thus $t \leq 2$ . But $n \leq t+1 \leq 3$ , thus $n=3, t=2$ , and $m=t+n=5$
To show that it works, just note that $x^5+x-1=(x^3+x^2-1)(x^2-x+1)$

Z K Y

The post below has been deleted. Click to close.

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

1730 posts

OronSH

#31 h Feb 27, 2025, 6:01 PM

Y by

By polynomial division if $x^n+x^2-1\nmid x^m+x-1$ then there is a remainder term which is eventually always smaller than the denominator, giving non integers. Thus $x^n+x^2-1\mid x^m+x-1$ . Rearranging, $x^n+x^2-1\mid\tfrac1x((x^m+x-1)-(x^n+x^2-1))+(x^m+x-1)=x^{n-1}(x^{m-n+1}+x^{m-n}-1)$ so $m-n+1\ge n$ . Now let $r$ be a root of $x^n+x^2-1$ with $0<r<1$ which exists by IVT. Then $r^m=1-r,r^n=1-r^2\implies r^{m-n}=\tfrac1{r+1}$ which is between $\tfrac 12$ and $1$ . However $r^n\le\tfrac12$ as otherwise $r^n+r^2-1>\tfrac12+\tfrac12-1=0$ . Thus $m-n<n$ . Together we have $m=2n-1$ , which implies $x^n+x^2-1\mid x^n+x^{n-1}-1$ , so $n=3,m=5$ is the only solution.

This post has been edited 1 time. Last edited by OronSH, Feb 27, 2025, 6:07 PM

Z K Y

The post below has been deleted. Click to close.

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

615 posts

#32 h Apr 25, 2025, 4:13 PM

Y by

Problem is equivalent to finding $m, n$ such that $a^n + a^2 - 1 \mid a^m + a - 1.$

Let $f(x) = x^m + x - 1, g(x) = x^n + x^2 - 1.$ Let $0 < r < 1$ be a real root to $g(x)$ . This exists by IVT. Hence, we must have that $f(r) = 0.$ I claim that $m < 2n.$

First, we have that $r^m + r = r^n + r^2 = 1.$ Rearranging, we have that $r(1 - r) = r^{n}(1 - r^{m - n}) = (1 - r^2)(1 - r^{m - n}).$ Hence, $r^{m - n + 1} + r^{m - n} = 1.$ Now, assume for the sake of contradiction, that $m \geq 2n.$ It follows that $r^{m - n + 1} + r^{m - n} < r^{n + 1} + r^{n} = r^{n + 1} + 1 - r < 1.$ Thus, we have that $m < 2n.$

We now simplify the problem a bit:
$\begin{align*} a^n + a^2 - 1 \mid a^m + a - 1 & \implies a^n + a^2 - 1 \mid (a^m + a - 1)(a + 1) \\ & \implies a^n + a^2 - 1 \mid a^{m + 1} + a^m - a^n \\ & \implies a^n + a^2 - 1 \mid a^{m - n + 1} + a^{m - n} - 1 \\ \end{align*}$ Hence, since $n < m < 2n,$ we have that the degree of the LHS is $m - n + 1 < n + 1.$ Hence, it must be $n,$ and so $m = 2n - 1.$ Hence, the only solution is $(5, 3)$ only.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a