Claim 1: Let $p$ be an arbitrary prime number. If $p$ divides two of the following numbers, it divides the third. \[a^n + bm \quad ; \quad a^{n + 1} - b^{n + 1} \quad ; \quad b^n + am\] If $p \mid a^n + bm$ and $p \mid b^n + am$, we have \[p \mid a(a^n + bm) - b(b^n + am) = a^{n + 1} - b^{n + 1}\] If $p \mid a^{n + 1} - b^{n + 1}$ and $p \mid a^n + bm$, we have \[p \mid a(a^n + bm) - (a^{n + 1} - b^{n + 1}) = b^{n + 1} - abm\]Since $\gcd(a, b) = 1$, we have $p \nmid b$ which implies $p \mid b^n + am$. Claim 2: Suppose we have fixed $n$. If positive integers $x$ and $y$ satisfy the following three conditions, then there exists $m$ such that $x = a^n + bm$ and $y = b^n + am$. $ax - by = a^{n + 1} - b^{n + 1}$ $x \equiv a^n \pmod{b}$ $x > a^n$ We can just write $x = a^n + bm$ and substituting it into $ax - by = a^{n + 1} - b^{n + 1}$ gives $y = b^n + am$. Our main idea is as follows. If we can find positive integers $(x, y)$, which do not divide each other, satisfying the conditions laid in Claim 2, with the additional constraint that all primes where $p \mid xy$ satisfy $p \mid a^{n + 1} - b^{n + 1}$, then Claim 1 gives us a construction. Indeed, if we write $x = a^n + bm$ and $y = b^n + am$, we can see that Claim 1 implies $\text{rad}(x) = \text{rad}(y)$. $(\clubsuit)$ We will now finish the problem. Without loss of generality, we can assume $a < b$. Suppose $ak + 1$ divides $bk + 1$. Then, $ak + 1 \mid k(b - a)$ which implies $ak + 1 \mid (b - a)$ and hence, $k \leq b - a$. Pick a sufficiently large $k$ divisible by $ab$. Note that $ak + 1 \nmid bk + 1$ and \[a(bk + 1) - b(ak + 1) = a - b\] Claim 3: There exists a positive integer $n$ such that $(ak + 1) (bk + 1) \mid a^n - b^n$. Given our choice of $k$, we have $p \nmid a$ and $p \nmid b$ for all primes $p$ that divide $(ak + 1)(bk + 1)$. Therefore, we can simply use Euler's theorem to force $a^n \equiv b^n \equiv 1 \pmod{(ak + 1) (bk + 1)}$. $\square$ Consider an $n > a$ which satisfies the conditions of Claim 3. Let $x = (bk + 1) \frac{a^n - b^n}{a-b}$ and $y = (ak + 1) \frac{a^n - b^n}{a - b}$. Note that \[\frac{a^n- b^n}{a - b} = a^{n - 1} + a^{n - 2}b + \dots + b^{n - 2}a + b^{n - 1} > n \cdot a^{n - 1} > a^n\]We also have $x \equiv a^{n - 1} \pmod{b}$ and $ax - by = a^{n} - b^n$. Let $p$ be a prime which divides $x$. We always have $p \mid a^{n} - b^n$. Observe that this gives us a construction for $n-1$ by $(\clubsuit)$, as desired. $\blacksquare$

rip IZHO (2005-2025)

rip logic

Attachments:

topologicalsort wrote: rip IZHO (2005-2025) Wdym?

Is this one the last IZHO?