Results 1 to 7 of 7

Thread: Reals & Integers

  1. #1
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7

    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}.$
    Follow Math Help Forum on Facebook and Google+

  2. #2
    AMI
    AMI is offline
    Junior Member AMI's Avatar
    Joined
    Jun 2009
    Posts
    40
    $\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..
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by AMI View Post
    $\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..
    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!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    AMI
    AMI is offline
    Junior Member AMI's Avatar
    Joined
    Jun 2009
    Posts
    40
    Oh-oh, $\displaystyle b$ acted sort of like a prime (sometimes). Sorry.
    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

    $\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}$.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
    $\displaystyle x-y $ divides $\displaystyle x^n-y^n $ for all $\displaystyle n>0 $. Maybe we can use that?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by AMI View Post
    Oh-oh, $\displaystyle b$ acted sort of like a prime (sometimes). Sorry.
    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

    $\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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    AMI
    AMI is offline
    Junior Member AMI's Avatar
    Joined
    Jun 2009
    Posts
    40
    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...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Aug 23rd 2010, 08:23 AM
  2. Replies: 7
    Last Post: Aug 3rd 2010, 01:31 PM
  3. Replies: 1
    Last Post: May 14th 2010, 01:53 AM
  4. Matrix of integers whose inverse is full of integers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Mar 19th 2010, 02:02 PM
  5. Are algebraic integers dense in the reals?
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Jun 24th 2009, 12:19 PM

Search Tags


/mathhelpforum @mathhelpforum