# 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
7 years, 4 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.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. 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 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> 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.

- 7 years, 4 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.

- 7 years, 4 months ago

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

How exactly?

- 7 years, 4 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 - 7 years, 4 months ago

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

- 7 years, 4 months ago

Very nice solution!

- 7 years, 4 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 - 7 years, 4 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.

- 7 years, 4 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 - 7 years, 4 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

- 7 years, 4 months ago

This was my method!

- 7 years, 4 months ago

I would greatly appreciate help too.

I am serious.

- 7 years, 4 months ago

You are totally 44

- 7 years, 4 months ago

you are totally 18

- 7 years, 4 months ago

You are totally 14

- 7 years, 4 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.

- 7 years, 4 months ago

13.

- 7 years, 4 months ago