Question

show that \(x^n-y^n\) is divisible by \(x-y\) for all \(n\in \mathbb{Z^+}\) using contradiction

\(x,y\) are distinct integers

Answer 1

IDK how haha

Answer 2

since this is a proof by contradiction i think we start by assuming the opposite is true :

suppose there exists some integer \(k\gt 0\) for which the given statement does not hold
\[\dfrac{x^k-y^k}{x-y} \not \in \mathbb{Z}\]

Answer 3

if x =y than x - y = 0 and we have error ))

Answer 4

thats a good catch, i think the question requires some modification

Answer 5

ive updated... see if it looks fine nw :)

Answer 6

here im trying to mimic the proof of sqrt(2) irrationality, specifically this infinite descent argument

http://en.wikipedia.org/wiki/Proof_by_infinite_descent#Irrationality_of_.E2.88.9A2

Answer 7

im still working on proof using contradiction by infinite descent at the moment
but i like to see other ways using contradiction too

Answer 8

let's suppose that exists an integer n_0 such that:
\[\large{x^{{n_0}}} - {y^{{n_0}}} = r\left( {x - y} \right) + q\]
where
\[\large \begin{gathered}
r = r\left( {x,y} \right) \hfill \\
q = q\left( {x,y} \right) \hfill \\
\end{gathered} \]
now we can write:
\[\large \begin{gathered}
{x^{2{n_0}}} - {y^{2{n_0}}} = \left( {{x^{{n_0}}} - {y^{{n_0}}}} \right)\left( {{x^{{n_0}}} + {y^{{n_0}}}} \right) = \hfill \\
= \left( {r\left( {x - y} \right) + q} \right)\left( {{x^{{n_0}}} + {y^{{n_0}}}} \right) = \hfill \\
= r\left( {x - y} \right)\left( {{x^{{n_0}}} + {y^{{n_0}}}} \right) + q\left( {{x^{{n_0}}} + {y^{{n_0}}}} \right) \hfill \\
\end{gathered} \]
so also
\[\large{x^{2{n_0}}} - {y^{2{n_0}}}\] is not divisible by (x-y)
and also:
\[\large{x^{4{n_0}}} - {y^{4{n_0}}}\] is not divisible by (x-y)
and so on...

Answer 9

That looks neat! but that only works for even powers right ?

Answer 10

yes!

Answer 11

your proof actually shows that if the given statemetn doesn't work for some \(n\), then it also doesn't work for any even multiple of \(n\)

pretty amazing!!!

Answer 12

thanks!

Answer 13

http://prntscr.com/6q7fbq

Answer 14

it says how come
we can say that
x^n0 + y^n0 is not divisible by (x-y) for all n

Answer 15

thats a good catch, i think we can fix it easily by using long division

Answer 16

Here is the complete proof using michele's idea+long division + infinite descent :

Answer 17

suppose there exists some integer \(k\gt 0\) for which the given statement doesn't hold. then :
\[\dfrac{x^k-y^k}{x-y} \not \in \mathbb{Z} \]

By long division we get
\[\dfrac{x^k-y^k}{x-y} = x^{k-1} + \left(\color{blue}{\dfrac{x^{k-1}-y^{k-1}}{x-y}} \right)y \]

Since \(x^{k-1}\) and \(y\) are integers, the blue part above must not be a integer for the left hand side to be a noninteger :
\[\color{blue}{\dfrac{x^{k-1}-y^{k-1}}{x-y}} \not \in \mathbb{Z}\]

Keep doing this till we reach
\[\color{blue}{\dfrac{x^{1}-y^{1}}{x-y}} \not \in \mathbb{Z}\]

Contradiction. \(\blacksquare\)

Answer 18

oo :)

Answer 19

I think that we can say that x^n_0+y^n0 is not divisible by x-y, using the mathematics induction principle @dan815

Answer 20

i think we can put every induction proof in this infinite descent form

Answer 21

i mean we can translate every induction proof into a contradiction proof using infinite descent

Answer 22

Wouldn't just directly factoring this work as well?

Answer 23

thats how we do it normally, this thread is dedicated to infinite descent technique though ;p

Answer 24

https://brilliant.org/wiki/general-diophantine-equations-fermats-method-of/#formulation-of-fermats-method-of-infinite-descent