Integer Difference of Powers

I'll just leave this here.

Patrick's approach of using the Lifting the Exponent lemma is a great way to solve the problem. We could still proceed pretty directly, though you can see why this approach motivates using LTE.

[This is not a complete solution.]

Hint 1: First show that $A, B$ are rational. In particular, counter examples are not "complex (but not real)" nor "irrational", so if you have found such a counter example, check a few values of $n$ first.
Hint 2: Set common denominator, IE $A = \frac{ N}{D}, b = \frac{M}{ D }$ . Show that if $p \mid D$ , then $p \mid N, M$ .
Hence, conclude that $a,b$ are integers.

---

[These are the details. Do not read ahead if you want to solve this yourself.]

Hint 1: Since $A - B \neq 0$ , thus $A + B = \frac{ A^2 - B^2 } { A+B}$ is rational. Hence, $A, B = \frac{ (A+B) \pm (A-B) } { 2}$ is also rational.

Hint 2: Note that we can multiply $A$ and $B$ by any integer, and still satisfy the conditions. Hence, we may assume that $p$ is a prime, and multiply throughout by $\frac{ D}{p}$ . Redefining notation, let $A = \frac{ N}{p} , B = \frac{ M} { p }$ , where $p$ is a prime (possibly 2).

To satisfy the conditions, $p \mid N \Leftrightarrow p \mid M$ . If so, both terms are integers and we are done. Henceforth, suppose that $p \not \mid N, p \not \mid M, N \neq M$ .

Let $A = p^kq + \frac{M}{p}$ where $p \not \mid q$ . Then,
$A^l - B^l = ( p^k q + \frac{M}{p} ) ^l - (\frac{M}{p} )^l = { l \choose 1} ( \frac{M}{p} ) ^{l-1} (p^kq)^1 + { l \choose 2} ( \frac{M}{p} ) ^{l-2} (p^kq)^2 + \ldots + { l \choose l-1} ( \frac{M}{p} ) ^{1} (p^kq)^{l-1} + (p^kq)^l .$

To reach a contradiction, the goal is to pick an $l$ such that the first term has much more powers of $p$ in the denominator than the subsequant terms, which means we actually have a fraction.
To achieve this, let $l = pz > k+2$ and $p \not \mid z$ (the reason for these conditions will become obvious soon). Multiplying throughout by $p^l$ , we obtain:
$p^l ( A^l - B^l) = { l \choose 1 } M^{l-1} p^k q + { l \choose 2} M^{l-2} p^{2k+1} q^2 + { l \choose 3 } M^{l-3} p^{3k+2} q^3 + \ldots + { l \choose l - 1 } M^{1} p^{kl -k + l -1 } + p^{kl+l} q^l$

From lucas' theorem / Kummer's theorem / manual verification, we know that

• $p \mid { l \choose i }$ for $1 \leq i \leq l-1$
• $p^2 \not \mid { l \choose 1 } = pz$

Hence, $p ^ { k + 1 }$ is the highest power of $p$ that divides ${ l \choose 1 } M^{l-1} p^k q$ and $p^{k+2}$ divides every subsequant term on the RHS. Hence $p^{k+2}$ does not divide the RHS.
This contradicts the fact that $p^ l > p^{k+2}$ divides the LHS.

---

Note: When trying to find counterexamples, we see that increasing the value of $k$ in $A - B = p^k q$ allows us to make the $A^n - B^n$ an integer for larger values of $n$ . E.g. Take $p = 2, A = 5.5, B = 4.5$ .
This is reflected in the solution, where the test value is set larger than $k + 2$ .

Note: Michael Mendrin's solution suggests using $l = p^z+ 1 > k$ . Can you complete the argument?
IE How does that change the solution from Lucas' Theorem onwards?

Note: We are very interested in calculating $v_p (N^n - M^n)$ , which is where the Lifting the Exponent Lemma comes in.

NOTE : There is a mistake in the solution. See if you can figure it out!

---

From Calvin's hint, we know that A and B are rationals.

Let $A = \frac{a}{b}$ and $B = \frac{c}{d}$ where $(a , b)$ and $(c,d)$ are coprime

Hence, $\frac{a^n}{b^n} - \frac{c^n}{d^n} = \frac{(ad)^n - (bc)^n}{(bd)^n}$

$\Rightarrow$ $(ad)^n - (bc)^n \equiv 0 \text{ } ( \text{mod}$ $(bd)^n )$

$\Rightarrow$ $(ad)^n \equiv (bc)^n \text{ } ( \text{mod}$ $(bd)^n)$

$\Rightarrow$ $ad \equiv \pm bc \text{ } ( \text{mod}$ $bd)$

This is only possible when $\frac{a}{b} = \frac{c}{d}$ $\Rightarrow$ $A = B$

Hence, $\boxed{ \text{ A and B must be integers}}$ $\blacksquare$

proof under construction

If the following are integers $x,y$

$a-b=x$
$a^2-b^2=y$

then we can deduce that

$a=\dfrac{1}{2x}(x^2+y)$
$b=\dfrac{1}{2x}(-x^2+y)$

which, if plugged into $2^{n-1} (a^n-b^n)$ , an integer, has the following term which must be an integer for $n>2$ (Warning: hand waving here! Involves induction)

$\dfrac{ny^{n-1}}{x^{n-2}}$

Muliplying all these terms results in the following product, which must also be an integer

$\frac{1}{2}n!\dfrac{y^{ \frac{1}{2}(n^2-n-2) }}{x^{ \frac{1}{2}(n^2-3n-2) }}$

where $n$ is unbounded.

Which means that if $x,y$ are finite integers, $y$ is an integer multiple of $x$ , say, $y=zx$ . Then we revise $a, b$

$a=\dfrac{1}{2}(x+z)$
$b=\dfrac{1}{2}(-x+z)$

(Warning: more hand waving follows, need to show details)

Now, if both $x, z$ are either even or odd, then $a,b$ are integers. We will examine what happens if $x,z$ are of different parity. We can revise $a,b$ in this form, where $p, q$ are integers

$a=\dfrac{1}{2}(2p+1+2q)$
$b=\dfrac{1}{2}(-2p-1+2q)$

Then when these are plugged into $2^{(n-2)}\left( a^n-b^n \right)$ for arbitrary odd $n$ , the result is always half integer. So, we can revise $a,b$ once more

$a=\dfrac{1}{2}(2p+2q+1)$
$b=\dfrac{1}{2}(-2p+2q+1)$

Then when these are plugged into $2^{(2^n-n-3)}\left( a^{(2^n+1)}-b^{(2^n+1)} \right)$ (notice the powers of 2) for arbitrary $n$ all the terms are integers except for the first which is of the form $\dfrac{(2^n+1)p}{2^{n+1}}$

which means that $p$ is divisible by $2^{n+1}$ , where $n$ is unbounded. Therefore, $a,b$ must both be integers, if finite.

Okay, so maybe this is easier to prove using modulo methods.

If we take √2 and √3, (√3)^2 - (√2)^2 = 1 and √2 and √3 are not integers...

sorry, i can't use latex well...

Let $A = Bx$ .

$(Bx)^{n} - B^{n}$

$B^{n}x^{n} - B^{n}$

$B^{n}(x^{n} - 1)$

This value must be an integer for every positive integer $n$ .

Say $B$ is $\frac{1}{3}$ , $\frac{4}{3}$ , or any other non-integer fraction with denominator $3$ . Given that for a certain value of $n$ , the above expression is an integer, as $n$ increases by $1$ , the denominator of $B^{n}$ is multiplied by $3$ , so $(x^{n} - 1)$ must be multiplied by a multiple of $3$ to cancel the fraction and keep the expression as an integer.

Generalizing, given that for a certain value of $n$ , the above expression is an integer, as $n$ increases by $1$ , the denominator of $B^{n}$ is multiplied by $\frac{1}{B}$ , so $(x^{n} - 1)$ must be multiplied by a multiple of $\frac{1}{B}$ to cancel the fraction and keep the expression as an integer. With this information, an equation representing this relationship can be created, where $C$ can be any positive integer, so that $C\frac{1}{B}$ represents any multiple of $\frac{1}{B}$

$C\dfrac{1}{B}(x^{n} - 1) = x^{n + 1} - 1$

$\dfrac{C}{B} = \dfrac{x^{n + 1} - 1}{x^{n} - 1}$

$\dfrac{B}{C} = \dfrac{x^{n} - 1}{x^{n + 1} - 1}$

$B = C\dfrac{x^{n} - 1}{x^{n + 1} - 1}$

However, this would imply that $B$ depends on which value of $n$ is chosen! This is a contradiction because $B$ is constant. The only values of $x$ which would keep $n$ from having any affect on $B$ are $x = 0, 1$ . If $x = 0$ , $A = B \cdot 0 = 0$ , an integer. If $x = 1$ , $A = B \cdot 1 = B$ , which is not possible since $A$ and $B$ are distinct.

Therefore, $A$ and $B$ must be integers.

Let's prove this by contradiction, so let $A^n-B^n \in \mathbb{Z}$ and $A \bigwedge B \not\in \mathbb{Z}$ for all $n \in \mathbb{Z}^+$ .

Then for $n=1$ , $A-B \in \mathbb{Z}$ .

And for $n=2$ , $A^2-B^2 = (A-B)(A+B) \in \mathbb{Z}$ which implies $A+B \in \mathbb{Z}$ .

And while we are at it (we'll need it later), for $n=4$ , $A^4-B^4=(A-B)(A+B)(A^2+B^2) \in \mathbb{Z}$ which implies $A^2+B^2 \in \mathbb{Z}$ .

Hence, we can let $A-B = n_1$ and $A+B = n_2$ with $n_1, n_2 \in \mathbb{Z}$ . Solving for $B$ , we can graph $A$ vs $B$ for various $n_1$ and $n_2$ .

Here the blue lines are $B=A-n_1$ and the green lines are $B=-A+n_2$ . It becomes immediately obvious using this representation that both $A$ and $B$ are half integer multiples. Further, via our assumption that $A$ or $B$ is not an integer, both must be non-integer in order that $A+B \in \mathbb{Z}$ .

Hence, let $A = m_a + 1/2$ and $B = m_b + 1/2$ with $m_a, m_b \in \mathbb{Z}$ . Then $A^2 + B^2 = (m_a + 1/2)^2 + (m_b + 1/2)^2 = {m_a}^2 + m_a + {m_b}^2 + m_b + 1/2 \not\in \mathbb{Z}$ , and we have a contradition.

Therefore, both $A$ and $B$ must be integers.

just suppose that n=1or2 for simplicity, then A=0.5 and B=0.25 ... but the answer isn't integer ... right?