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.
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.
Markdown
Appears as
*italics* or _italics_
italics
**bold** or __bold__
bold
- bulleted - list
bulleted
list
1. numbered 2. list
numbered
list
Note: you must add a full line of space before and after lists for them to show up correctly
# 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"
Math
Appears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3
2×3
2^{34}
234
a_{i-1}
ai−1
\frac{2}{3}
32
\sqrt{2}
2
\sum_{i=1}^3
∑i=13
\sin \theta
sinθ
\boxed{123}
123
Comments
If x and y are irrational then there is no way that the initial integer conditions hold, so let us write x=ma and y=nb where gcd(a,m)=gcd(b,n)=1. Let us assume that m=n, ie, there is some prime factor in m which is not in n. Then x+y=ma+nb=mnan+bm. Considering the numerator, an+bm≡an(modm) but there is a prime factor in m which is not in n and gcd(a,m)=1 so an≡0(modm) 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=ma and y=mb where again gcd(a,m)=gcd(b,m)=1.
We have that x+y is an integer so a+b≡0(modm) so a≡−b(modm). Squaring both sides of the congruence gives a2≡b2(modm). But we also have that x2+y2 is an integer so a2+b2≡0(modm) so a2≡−b2(modm) (in fact a2+b2≡0(modm2) but that is less useful to us). Combining these congruences gives b2≡−b2(modm) so 2b2≡0(modm). 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 a2+b2≡2(mod4) but x2+y2=4a2+b2 so that means that x2+y2 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.
Oh, in fact, I can produce a counterexample to your claim: x=2,y=−2 satisfies the conditions of the problem but not your claim that x,y are integers.
Another statement which is not true is "Let us assume that m=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≡0(modm), which contradicts your conclusion. This could be fixed though, with better bookkeeping of the variables.
The key step is to show that xy is an integer, and then use (strong) Induction on the algebraic identity
xn+1+yn+1=(x+y)(xn+yn)−xy(xn−1+yn−1).
Note that you have to use the x4+y4 condition, as just the first three are not strong enough. For example, using x=22,y=−22, gives us x+y=0,x2+y2=1,x3+y3=0 but x4+y4=21 (and the higher even powers clearly do not yield integers).
We use the identity xn+yn=(x+y)(xn−1+yn−1)−xy(xn−2+yn−2).
First we prove that xy is an integer. Note that 2xy=(x+y)2−(x2+y2)∈Z and 2x2y2=(x2+y2)2−(x4+y4)∈Z. From the first equation we see that 2xy=m for some integer m, so xy=2m. From the second equation we have 2x2y2=n for some integer n. Plugging xy=2m yields 2(4m2)=n⇔2m2=n∈Z. So 2∣m. Hence xy=2m∈Z, as desired. //
Now, let p(n)=true⇒xn+yn∈Z. By the identity, p(1),p(n−1),xy,p(n−2)⇒p(n). So p(1),p(4),xy,p(3)⇒p(5); p(1),p(5),xy,p(4)⇒p(6), and by a straight-forward strong induction on n, p(n)=true∀n∈N. □
Easy Math Editor
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:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.2 \times 3
2^{34}
a_{i-1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
If x and y are irrational then there is no way that the initial integer conditions hold, so let us write x=ma and y=nb where gcd(a,m)=gcd(b,n)=1. Let us assume that m=n, ie, there is some prime factor in m which is not in n. Then x+y=ma+nb=mnan+bm. Considering the numerator, an+bm≡an(modm) but there is a prime factor in m which is not in n and gcd(a,m)=1 so an≡0(modm) 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=ma and y=mb where again gcd(a,m)=gcd(b,m)=1.
We have that x+y is an integer so a+b≡0(modm) so a≡−b(modm). Squaring both sides of the congruence gives a2≡b2(modm). But we also have that x2+y2 is an integer so a2+b2≡0(modm) so a2≡−b2(modm) (in fact a2+b2≡0(modm2) but that is less useful to us). Combining these congruences gives b2≡−b2(modm) so 2b2≡0(modm). 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 a2+b2≡2(mod4) but x2+y2=4a2+b2 so that means that x2+y2 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.
Log in to reply
Oh, in fact, I can produce a counterexample to your claim: x=2,y=−2 satisfies the conditions of the problem but not your claim that x,y are integers.
How exactly?
Another statement which is not true is "Let us assume that m=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≡0(modm), which contradicts your conclusion. This could be fixed though, with better bookkeeping of the variables.
Log in to reply
I was considering WLOG ( m > n ) and so either a prime factor or prime exponent are different which gives the same result
Very nice solution!
The key step is to show that xy is an integer, and then use (strong) Induction on the algebraic identity
xn+1+yn+1=(x+y)(xn+yn)−xy(xn−1+yn−1).
Note that you have to use the x4+y4 condition, as just the first three are not strong enough. For example, using x=22,y=−22, gives us x+y=0,x2+y2=1,x3+y3=0 but x4+y4=21 (and the higher even powers clearly do not yield integers).
Log in to reply
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.
Log in to reply
To get that xy is half an integer, you only used the first 2 conditions. Namely,
2xy=(x+y)2−(x2+y2)∈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).
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
This was my method!
I would greatly appreciate help too.
I am serious.
Log in to reply
You are totally 44
Log in to reply
you are totally 18
Log in to reply
Log in to reply
Log in to reply
We use the identity xn+yn=(x+y)(xn−1+yn−1)−xy(xn−2+yn−2).
First we prove that xy is an integer. Note that 2xy=(x+y)2−(x2+y2)∈Z and 2x2y2=(x2+y2)2−(x4+y4)∈Z. From the first equation we see that 2xy=m for some integer m, so xy=2m. From the second equation we have 2x2y2=n for some integer n. Plugging xy=2m yields 2(4m2)=n⇔2m2=n∈Z. So 2∣m. Hence xy=2m∈Z, as desired. //
Now, let p(n)=true⇒xn+yn∈Z. By the identity, p(1),p(n−1),xy,p(n−2)⇒p(n). So p(1),p(4),xy,p(3)⇒p(5); p(1),p(5),xy,p(4)⇒p(6), and by a straight-forward strong induction on n, p(n)=true ∀n∈N. □
STATE YOUR SOURCE