Results 1 to 7 of 7

Math Help - Reals & Integers

  1. #1
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7

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

  2. #2
    AMI
    AMI is offline
    Junior Member AMI's Avatar
    Joined
    Jun 2009
    Posts
    40
    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}<br />
\Rightarrow b\mid ad-bc\Rightarrow b\mid ad\stackrel{\text{(4)}}{\Longrightarrow}b\mid d\\<br />
\Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b<br />
\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..
    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
    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}<br />
\Rightarrow b\mid ad-bc\Rightarrow b\mid ad\stackrel{\text{(4)}}{\Longrightarrow}b\mid d\\<br />
\Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b<br />
\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..
    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!
    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, 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

    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}<br />
\Rightarrow b\mid ad-bc\Rightarrow b\mid ad\stackrel{\text{(4)}}{\Longrightarrow}b\mid d\\<br />
\Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b<br />
\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}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Sampras's Avatar
    Joined
    May 2009
    Posts
    301
     x-y divides  x^n-y^n for all  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, 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

    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}<br />
\Rightarrow b\mid ad-bc\Rightarrow b\mid ad\stackrel{\text{(4)}}{\Longrightarrow}b\mid d\\<br />
\Rightarrow d\mid ad-bc\Rightarrow d\mid bc\stackrel{\text{(4)}}{\Longrightarrow}d\mid b<br />
\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.
    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 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...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum