Waste less time on Facebook — follow Brilliant.
×

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

No vote yet
1 vote

  Easy Math Editor

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

[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} \)

Comments

Sort by:

Top Newest

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).

Calvin Lin Staff - 3 years, 9 months ago

Log in to reply

This was my method!

Wei Jie Tan - 3 years, 9 months ago

Log in to reply

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

Victor Loh - 3 years, 9 months ago

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.

Ivan Koswara - 3 years, 9 months ago

Log in to reply

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).

Calvin Lin Staff - 3 years, 9 months ago

Log in to reply

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.

Josh Rowley - 3 years, 9 months ago

Log in to reply

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.

Ivan Koswara - 3 years, 9 months ago

Log in to reply

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.

Calvin Lin Staff - 3 years, 9 months ago

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

Josh Rowley - 3 years, 9 months ago

Log in to reply

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

How exactly?

Ivan Koswara - 3 years, 9 months ago

Log in to reply

Very nice solution!

Cody Johnson - 3 years, 9 months ago

Log in to reply

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\)

Arkan Megraoui - 3 years, 8 months ago

Log in to reply

I would greatly appreciate help too.

I am serious.

Yuxuan Seah - 3 years, 9 months ago

Log in to reply

You are totally 44

Wei Jie Tan - 3 years, 9 months ago

Log in to reply

you are totally 18

Victor Loh - 3 years, 9 months ago

Log in to reply

@Victor Loh You are totally 14

Wei Jie Tan - 3 years, 9 months ago

Log in to reply

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

Yuxuan Seah - 3 years, 9 months ago

Log in to reply

@Yuxuan Seah 13.

Wei Jie Tan - 3 years, 9 months ago

Log in to reply

STATE YOUR SOURCE

Wei Jie Tan - 3 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...