How to prove???

Let $x$ and $y$ be real numbers such that $x+y, x^{2}+y^{2}, x^{3}+y^{3}$ and $x^{4}+y^{4}$ are integers. If $n$ is a natural number, prove that $x^{n}+y^{n}$ is an integer.

Help would be greatly appreciated! Note by Victor Loh
5 years, 7 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
• Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

• bulleted
• list

1. numbered
2. list

1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

> This is a quote
This is a quote
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

If $x$ and $y$ are irrational then there is no way that the initial integer conditions hold, so let us write $x = \dfrac{a}{m}$ and $y = \dfrac{b}{n}$ where $gcd(a,m) = gcd(b,n) = 1$. Let us assume that $m \ne n$, ie, there is some prime factor in $m$ which is not in $n$. Then $x + y = \dfrac{a}{m} + \dfrac{b}{n} = \dfrac{an+bm}{mn}$. Considering the numerator, $an + bm \equiv an \pmod{m}$ but there is a prime factor in $m$ which is not in $n$ and $gcd(a,m) = 1$ so $an \not\equiv 0 \pmod{m}$ ie. the numerator can't be divisible by $m$ and so $x + y$ is not an integer. Therefore our assumption was wrong so $x$ and $y$ have the same denominator. So we will rewrite them as $x = \dfrac{a}{m}$ and $y = \dfrac{b}{m}$ where again $gcd(a,m) = gcd(b,m) = 1$.

We have that $x + y$ is an integer so $a + b \equiv 0 \pmod{m}$ so $a \equiv -b \pmod{m}$. Squaring both sides of the congruence gives $a^2 \equiv b^2 \pmod{m}$. But we also have that $x^2 + y^2$ is an integer so $a^2 + b^2 \equiv 0 \pmod{m}$ so $a^2 \equiv -b^2 \pmod{m}$ (in fact $a^2 + b^2 \equiv 0 \pmod{m^2}$ but that is less useful to us). Combining these congruences gives $b^2 \equiv -b^2 \pmod{m}$ so $2b^2 \equiv 0 \pmod{m}$. But $gcd(b,m) = 1$, so either $m = 1$ or $m = 2$.

If $m = 1$ then the result is trivial (since $x$ and $y$ themselves are integers ). If $m = 2$ then $a$ and $b$ are odd, so $a^2 + b^2 \equiv 2 \pmod{4}$ but $x^2 + y^2 = \dfrac{a^2 + b^2}{4}$ so that means that $x^2 + y^2$ is not an integer.

So your initial set of conditions only hold if $x$ and $y$ are integers themselves, following which the result is obvious.

- 5 years, 7 months ago

Oh, in fact, I can produce a counterexample to your claim: $x = \sqrt{2}, y = -\sqrt{2}$ satisfies the conditions of the problem but not your claim that $x,y$ are integers.

- 5 years, 7 months ago

If $x$ and $y$ are irrational then there is no way that the initial integer conditions hold

How exactly?

- 5 years, 7 months ago

Another statement which is not true is "Let us assume that $m\neq n$, i.e., there is some prime factor in $m$ which is not in $n$." The IE part doesn't necessarily follow from the assumption. For example, take $m = 2, n = 4$. Note that with these values, we have $an \equiv 0 \pmod{m}$, which contradicts your conclusion. This could be fixed though, with better bookkeeping of the variables.

Staff - 5 years, 7 months ago

I was considering WLOG ( m > n ) and so either a prime factor or prime exponent are different which gives the same result

- 5 years, 7 months ago

Very nice solution!

- 5 years, 7 months ago

The key step is to show that $xy$ is an integer, and then use (strong) Induction on the algebraic identity

$x^{n+1} + y^{n+1} = (x+y) (x^n + y^n) - xy ( x^{n-1} + y^{n-1} ).$

Note that you have to use the $x^4 + y^4$ condition, as just the first three are not strong enough. For example, using $x = \frac{\sqrt{2}}{2}, y = - \frac{ \sqrt{2} } {2}$, gives us $x+y = 0, x^2 + y^2 = 1, x^3 + y^3 = 0$ but $x^4 + y^4 = \frac{1}{2}$ (and the higher even powers clearly do not yield integers).

Staff - 5 years, 7 months ago

I haven't found how to get $xy$ is an integer; I only got $xy$ is half an integer. I'm still figuring out how to get past that.

- 5 years, 7 months ago

To get that $xy$ is half an integer, you only used the first 2 conditions. Namely,

$2xy = (x+y)^2 - (x^2 + y^2 ) \in \mathbb{N}.$

Use the "hint" that you must use the 4th condition. Somehow or other, it must come into play (and it does, in a very similar manner).

Staff - 5 years, 7 months ago

Hi Calvin

When I was doing the problem I also got stuck with xy. But can u further elaborate on the later part of your hint? Thanks

- 5 years, 7 months ago

This was my method!

- 5 years, 7 months ago

I would greatly appreciate help too.

I am serious.

- 5 years, 7 months ago

You are totally 44

- 5 years, 7 months ago

you are totally 18

- 5 years, 7 months ago

You are totally 14

- 5 years, 7 months ago

Come on my age is wrong... I am victor's classmate. Our homework for math was this question. So yeah, I am 14.

- 5 years, 7 months ago

13.

- 5 years, 7 months ago

We use the identity $x^n+y^n=(x+y)(x^{n-1}+y^{n-1})-xy(x^{n-2}+y^{n-2})$.

First we prove that $xy$ is an integer. Note that $2xy=(x+y)^2-(x^2+y^2)\in \mathbb{Z}$ and $2x^2y^2=(x^2+y^2)^2-(x^4+y^4)\in \mathbb{Z}$. From the first equation we see that $2xy=m$ for some integer $m$, so $xy=\frac{m}{2}$. From the second equation we have $2x^2y^2=n$ for some integer $n$. Plugging $xy=\frac{m}{2}$ yields $2\left(\frac{m^2}{4}\right)=n\Leftrightarrow \frac{m^2}{2}=n\in \mathbb{Z}$. So $2\mid m$. Hence $xy=\frac{m}{2}\in \mathbb{Z}$, as desired. //

Now, let $p(n)=\text{true}\Rightarrow x^n+y^n\in \mathbb{Z}$. By the identity, $p(1), p(n-1), xy, p(n-2)\Rightarrow p(n)$. So $p(1), p(4), xy, p(3)\Rightarrow p(5)$; $p(1), p(5), xy, p(4)\Rightarrow p(6)$, and by a straight-forward strong induction on $n$, $p(n)=\text{true}\ \forall n\in \mathbb{N}$. $\Box$

- 5 years, 6 months ago