# Reals & Integers

• June 25th 2009, 12:14 PM
NonCommAlg
Reals & Integers
This problem is pretty: Suppose $x \neq y$ are in $\mathbb{R}$ and $x^n - y^n \in \mathbb{Z},$ for all $n \in \mathbb{N}.$ Prove that $x,y \in \mathbb{Z}.$
• June 26th 2009, 02:16 AM
AMI
$n:=1\Longrightarrow x-y\in\mathbb{Z}$ (1)
$n:=2\Longrightarrow x^2-y^2\in\mathbb{Z}$ (2)
(1),(2) $\Longrightarrow x+y\in\mathbb{Q}$ (3)
(1),(3) $\Longrightarrow x,y\in\mathbb{Q}$; let $x=\frac{a}{b},y=\frac{c}{d}$ with $a,c\in\mathbb{Z},b,d\in\mathbb{N}\setminus\{0\}$
and $(a,b)=1,(c,d)=1$ (4)

$\bullet\;x-y=\frac{a}{b}-\frac{c}{d}=\frac{ad-bc}{bd}\in\mathbb{Z}\Rightarrow bd\mid ad-bc\Rightarrow$
$\begin{cases}
\Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b
\end{cases}$

$\Longrightarrow d=b\Rightarrow x-y=\frac{a-c}{b}\in\mathbb{Z}\Rightarrow b\mid a-c$ (5)
$\bullet\;x^2-y^2=\frac{(a-c)(a+c)}{b^2}\in\mathbb{Z}$.

Case 1: $b^2\nmid a-c$. This implies $b\mid a+c\stackrel{\text{(5)}}{\Longrightarrow}b\mid 2a\stackrel{\text{(4)}}{\Longrightarrow}b\mid 2\Rightarrow b=1,2$
If $b=2\stackrel{\text{(4)}}{\Longrightarrow}a,c$ are odd.
$x^3-y^3=\frac{(a-c)(a^2+ac+b^2)}{8}\in\mathbb{Z}$. We have $4=b^2\nmid a-c\Rightarrow4\mid a^2+ac+b^2$ false because it is odd.
We are then left with $b=1$ which means that $x,y\in\mathbb{Z}$.

Case 2: $b^2\mid a-c$. By induction, we prove that $b^n\mid a-c,\forall n$:
Fix $n$ and suppose $b^{n-1}\mid a-c$ but $b^n\nmid a-c$.
$x^n-y^n=\frac{(a-c)(a^{n-1}+a^{n-2}c+\dots+c^{n-1})}{b^n}\in\mathbb{Z}\Rightarrow b\mid a^{n-1}+a^{n-2}c+\dots+c^{n-1}$ (6)
$x^{n+1}-y^{n+1}=\frac{(a-c)(a^n+a^{n-1}c+\dots+c^n)}{b^{n+1}}\in\mathbb{Z}$. If $b\mid a^n+a^{n-1}c+\dots+ac^{n-1}+c^n\stackrel{\text{(6)}}{\Longrightarrow}b\mid c^n$ false
$\Rightarrow b^{n+1}\mid a-c$ - contradiction with $b^n\nmid a-c$.
So $b^n\mid a-c,\forall n\Rightarrow b=1\Rightarrow x,y\in\mathbb{Z}$.

Kind of long.. I hope it's correct though..(Worried)
• June 26th 2009, 04:08 AM
NonCommAlg
Quote:

Originally Posted by AMI
$n:=1\Longrightarrow x-y\in\mathbb{Z}$ (1)
$n:=2\Longrightarrow x^2-y^2\in\mathbb{Z}$ (2)
(1),(2) $\Longrightarrow x+y\in\mathbb{Q}$ (3)
(1),(3) $\Longrightarrow x,y\in\mathbb{Q}$; let $x=\frac{a}{b},y=\frac{c}{d}$ with $a,c\in\mathbb{Z},b,d\in\mathbb{N}\setminus\{0\}$
and $(a,b)=1,(c,d)=1$ (4)

$\bullet\;x-y=\frac{a}{b}-\frac{c}{d}=\frac{ad-bc}{bd}\in\mathbb{Z}\Rightarrow bd\mid ad-bc\Rightarrow$
$\begin{cases}
\Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b
\end{cases}$

$\Longrightarrow d=b\Rightarrow x-y=\frac{a-c}{b}\in\mathbb{Z}\Rightarrow b\mid a-c$ (5)
$\bullet\;x^2-y^2=\frac{(a-c)(a+c)}{b^2}\in\mathbb{Z}$.

Case 1: $b^2\nmid a-c$. This implies $b\mid a+c\stackrel{\text{(5)}}{\Longrightarrow}b\mid 2a\stackrel{\text{(4)}}{\Longrightarrow}b\mid 2\Rightarrow b=1,2$
If $b=2\stackrel{\text{(4)}}{\Longrightarrow}a,c$ are odd.
$x^3-y^3=\frac{(a-c)(a^2+ac+b^2)}{8}\in\mathbb{Z}$. We have $4=b^2\nmid a-c\Rightarrow4\mid a^2+ac+b^2$ false because it is odd.
We are then left with $b=1$ which means that $x,y\in\mathbb{Z}$.

Case 2: $b^2\mid a-c$. By induction, we prove that $b^n\mid a-c,\forall n$:
Fix $n$ and suppose $b^{n-1}\mid a-c$ but $b^n\nmid a-c$.
$x^n-y^n=\frac{(a-c)(a^{n-1}+a^{n-2}c+\dots+c^{n-1})}{b^n}\in\mathbb{Z}\Rightarrow b\mid a^{n-1}+a^{n-2}c+\dots+c^{n-1}$ (6)
$x^{n+1}-y^{n+1}=\frac{(a-c)(a^n+a^{n-1}c+\dots+c^n)}{b^{n+1}}\in\mathbb{Z}$. If $b\mid a^n+a^{n-1}c+\dots+ac^{n-1}+c^n\stackrel{\text{(6)}}{\Longrightarrow}b\mid c^n$ false
$\Rightarrow b^{n+1}\mid a-c$ - contradiction with $b^n\nmid a-c$.
So $b^n\mid a-c,\forall n\Rightarrow b=1\Rightarrow x,y\in\mathbb{Z}$.

Kind of long.. I hope it's correct though..(Worried)

it's correct up to the beginning of Case 1: your implication is not correct, i.e. it is possible to have $b^2 \mid uv, \ b \mid u, \ b^2 \nmid u$ and $b \nmid v.$ for example: b = 6, u = 18, v = 2. i'm sure you can fix this! (Nod)
• June 26th 2009, 05:52 AM
AMI
Oh-oh, $b$ acted sort of like a prime (sometimes). Sorry. (Blush)
I'll try again, and if it's still not good, then I'll better stop and leave it for someone else.. I'm sorry for wasting your time if I made some mistakes again (Sadsmile)

$n:=1\Longrightarrow x-y\in\mathbb{Z}$ (1)
$n:=2\Longrightarrow x^2-y^2\in\mathbb{Z}$ (2)
(1),(2) $\Longrightarrow x+y\in\mathbb{Q}$ (3)
(1),(3) $\Longrightarrow x,y\in\mathbb{Q}$; let $x=\frac{a}{b},y=\frac{c}{d}$ with $a,c\in\mathbb{Z},b,d\in\mathbb{N}\setminus\{0\}$
and $(a,b)=1,(c,d)=1$ (4)

$x-y=\frac{a}{b}-\frac{c}{d}=\frac{ad-bc}{bd}\in\mathbb{Z}\Rightarrow bd\mid ad-bc\Rightarrow$
$\begin{cases}
\Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b
\end{cases}$

$\Longrightarrow d=b$
I left this part unchanged. And now:

Suppose $b$ is even. This implies $a$ and $c$ odd, hence $\frac{a^n-c^n}{a-c}$ is odd for every odd $n$. But $b^n\mid a^n-c^n$, so we get $2^n\mid a-c$ for every odd $n$ - impossible. This means that $b$ must be odd.

$x-y=\frac{a-c}{b}\in\mathbb{Z}\Rightarrow b\mid a-c\Rightarrow a-c=kb,k\in\mathbb{Z}$
$x^2-y^2=\frac{(a-c)(a+c)}{b^2}\in\mathbb{Z}\Rightarrow b^2\mid (a-c)(a+c)=kb(2c+kb)\Rightarrow b\mid 2ck$. Having $(b,2)=1$ and $(b,c)=1$, we get $b\mid k$, so $b^2\mid a-c$.

By induction, we show that $b^n\mid a-c,\forall n$.
Suppose $b^{n-1}\mid a-c$. Then, $a-c=kb^{n-1},k\in\mathbb{Z}\Rightarrow a=c+kb^{n-1}$.
$b^n\mid a^n-c^n=kb^{n-1}\big((c+kb^{n-1})^{n-1}+(c+kb^{n-1})^{n-2}c+\dots+(c+kb^{n-1})c^{n-2}+c^{n-1}\big)$.
$\Rightarrow b\mid k\big(Kb+c^{n-1}+c^{n-2}c+\dots+c\cdot c^{n-2}+c^{n-1}\big)$, where $K\in\mathbb{Z}$.
$\Rightarrow b\mid k(Kb+nc^{n-1})\Rightarrow b\mid knc^{n-1}$.
$n$ is fixed arbitrarily and $(b,c)=1$, so $b\mid k\Longrightarrow b^n\mid a-c$.
$\Rightarrow b^n\mid a-c,\forall n\Rightarrow b=1\Rightarrow x,y\in\mathbb{Z}$.
• June 26th 2009, 10:28 AM
Sampras
$x-y$ divides $x^n-y^n$ for all $n>0$. Maybe we can use that?
• June 26th 2009, 03:37 PM
NonCommAlg
Quote:

Originally Posted by AMI
Oh-oh, $b$ acted sort of like a prime (sometimes). Sorry. (Blush)
I'll try again, and if it's still not good, then I'll better stop and leave it for someone else.. I'm sorry for wasting your time if I made some mistakes again (Sadsmile)

$n:=1\Longrightarrow x-y\in\mathbb{Z}$ (1)
$n:=2\Longrightarrow x^2-y^2\in\mathbb{Z}$ (2)
(1),(2) $\Longrightarrow x+y\in\mathbb{Q}$ (3)
(1),(3) $\Longrightarrow x,y\in\mathbb{Q}$; let $x=\frac{a}{b},y=\frac{c}{d}$ with $a,c\in\mathbb{Z},b,d\in\mathbb{N}\setminus\{0\}$
and $(a,b)=1,(c,d)=1$ (4)

$x-y=\frac{a}{b}-\frac{c}{d}=\frac{ad-bc}{bd}\in\mathbb{Z}\Rightarrow bd\mid ad-bc\Rightarrow$
$\begin{cases}
\Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b
\end{cases}$

$\Longrightarrow d=b$
I left this part unchanged. And now:

Suppose $b$ is even. This implies $a$ and $c$ odd, hence $\frac{a^n-c^n}{a-c}$ is odd for every odd $n$. But $b^n\mid a^n-c^n$, so we get $2^n\mid a-c$ for every odd $n$ - impossible. This means that $b$ must be odd.

$x-y=\frac{a-c}{b}\in\mathbb{Z}\Rightarrow b\mid a-c\Rightarrow a-c=kb,k\in\mathbb{Z}$
$x^2-y^2=\frac{(a-c)(a+c)}{b^2}\in\mathbb{Z}\Rightarrow b^2\mid (a-c)(a+c)=kb(2c+kb)\Rightarrow b\mid 2ck$. Having $(b,2)=1$ and $(b,c)=1$, we get $b\mid k$, so $b^2\mid a-c$.

By induction, we show that $b^n\mid a-c,\forall n$.
Suppose $b^{n-1}\mid a-c$. Then, $a-c=kb^{n-1},k\in\mathbb{Z}\Rightarrow a=c+kb^{n-1}$.
$b^n\mid a^n-c^n=kb^{n-1}\big((c+kb^{n-1})^{n-1}+(c+kb^{n-1})^{n-2}c+\dots+(c+kb^{n-1})c^{n-2}+c^{n-1}\big)$.
$\Rightarrow b\mid k\big(Kb+c^{n-1}+c^{n-2}c+\dots+c\cdot c^{n-2}+c^{n-1}\big)$, where $K\in\mathbb{Z}$.
$\Rightarrow b\mid k(Kb+nc^{n-1})\Rightarrow b\mid knc^{n-1}$.
$\color{red}(*)$ $n$ is fixed arbitrarily and $(b,c)=1$, so $b\mid k\Longrightarrow b^n\mid a-c$.
$\Rightarrow b^n\mid a-c,\forall n\Rightarrow b=1\Rightarrow x,y\in\mathbb{Z}$.

the line marked $\color{red}(*)$ is not quite right because you're fixing an $n,$ which might have a common divisor with $b.$ my solution: as you showed $b=d.$ suppose $b > 1$ and choose a prime divisor $p$ of $b.$

let $n$ be any positive integer such that $p \nmid n.$ since $p \mid a-c,$ we have $\frac{a^n-c^n}{a-c}=a^{n-1}+a^{n-2}c + \cdots + c^{n-1} \equiv nc^{n-1} \mod p.$ thus $p \nmid \frac{a^n-c^n}{a-c}.$ but we know $p^n \mid a^n - c^n=(a-c)\frac{a^n-c^n}{a-c}.$

thus $p^n \mid a-c,$ for all positive integers $n$ not divisible by $p,$ which is impossible.
• June 27th 2009, 12:49 AM
AMI
Yes, thank you. And for your clear solution, too.
I guess, since $b$ is fixed, I could have chosen to show that $b^n\mid a-c$ only for those $n$ with $(n,b)=1$ ...

Thanks again, sorry for my mistakes. I'll try to do better next time... (Speechless)