# Reals & Integers

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

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

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

Case 2: $\displaystyle b^2\mid a-c$. By induction, we prove that $\displaystyle b^n\mid a-c,\forall n$:
Fix $\displaystyle n$ and suppose $\displaystyle b^{n-1}\mid a-c$ but $\displaystyle b^n\nmid a-c$.
$\displaystyle 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)
$\displaystyle 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 $\displaystyle b\mid a^n+a^{n-1}c+\dots+ac^{n-1}+c^n\stackrel{\text{(6)}}{\Longrightarrow}b\mid c^n$ false
$\displaystyle \Rightarrow b^{n+1}\mid a-c$ - contradiction with $\displaystyle b^n\nmid a-c$.
So $\displaystyle 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)
• Jun 26th 2009, 04:08 AM
NonCommAlg
Quote:

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

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

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

Case 2: $\displaystyle b^2\mid a-c$. By induction, we prove that $\displaystyle b^n\mid a-c,\forall n$:
Fix $\displaystyle n$ and suppose $\displaystyle b^{n-1}\mid a-c$ but $\displaystyle b^n\nmid a-c$.
$\displaystyle 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)
$\displaystyle 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 $\displaystyle b\mid a^n+a^{n-1}c+\dots+ac^{n-1}+c^n\stackrel{\text{(6)}}{\Longrightarrow}b\mid c^n$ false
$\displaystyle \Rightarrow b^{n+1}\mid a-c$ - contradiction with $\displaystyle b^n\nmid a-c$.
So $\displaystyle 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 $\displaystyle b^2 \mid uv, \ b \mid u, \ b^2 \nmid u$ and $\displaystyle b \nmid v.$ for example: b = 6, u = 18, v = 2. i'm sure you can fix this! (Nod)
• Jun 26th 2009, 05:52 AM
AMI
Oh-oh, $\displaystyle 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)

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

$\displaystyle x-y=\frac{a}{b}-\frac{c}{d}=\frac{ad-bc}{bd}\in\mathbb{Z}\Rightarrow bd\mid ad-bc\Rightarrow$
$\displaystyle \begin{cases} \Rightarrow b\mid ad-bc\Rightarrow b\mid ad\stackrel{\text{(4)}}{\Longrightarrow}b\mid d\\ \Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b \end{cases}$
$\displaystyle \Longrightarrow d=b$
I left this part unchanged. And now:

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

$\displaystyle x-y=\frac{a-c}{b}\in\mathbb{Z}\Rightarrow b\mid a-c\Rightarrow a-c=kb,k\in\mathbb{Z}$
$\displaystyle 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 $\displaystyle (b,2)=1$ and $\displaystyle (b,c)=1$, we get $\displaystyle b\mid k$, so $\displaystyle b^2\mid a-c$.

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

Originally Posted by AMI
Oh-oh, $\displaystyle 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)

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

$\displaystyle x-y=\frac{a}{b}-\frac{c}{d}=\frac{ad-bc}{bd}\in\mathbb{Z}\Rightarrow bd\mid ad-bc\Rightarrow$
$\displaystyle \begin{cases} \Rightarrow b\mid ad-bc\Rightarrow b\mid ad\stackrel{\text{(4)}}{\Longrightarrow}b\mid d\\ \Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b \end{cases}$
$\displaystyle \Longrightarrow d=b$
I left this part unchanged. And now:

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

$\displaystyle x-y=\frac{a-c}{b}\in\mathbb{Z}\Rightarrow b\mid a-c\Rightarrow a-c=kb,k\in\mathbb{Z}$
$\displaystyle 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 $\displaystyle (b,2)=1$ and $\displaystyle (b,c)=1$, we get $\displaystyle b\mid k$, so $\displaystyle b^2\mid a-c$.

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

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

let $\displaystyle n$ be any positive integer such that $\displaystyle p \nmid n.$ since $\displaystyle p \mid a-c,$ we have $\displaystyle \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 $\displaystyle p \nmid \frac{a^n-c^n}{a-c}.$ but we know $\displaystyle p^n \mid a^n - c^n=(a-c)\frac{a^n-c^n}{a-c}.$

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

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