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!

#MathematicalInduction

Note by Victor Loh
7 years, 3 months ago

No vote yet
1 vote

  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:

  • 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

[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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

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

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

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

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

Josh Rowley - 7 years, 3 months ago

Log in to reply

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

Ivan Koswara - 7 years, 3 months ago

If xx and yy are irrational then there is no way that the initial integer conditions hold

How exactly?

Ivan Koswara - 7 years, 3 months ago

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

Calvin Lin Staff - 7 years, 3 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 - 7 years, 3 months ago

Very nice solution!

Cody Johnson - 7 years, 3 months ago

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

xn+1+yn+1=(x+y)(xn+yn)xy(xn1+yn1). 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 x4+y4 x^4 + y^4 condition, as just the first three are not strong enough. For example, using x=22,y=22 x = \frac{\sqrt{2}}{2}, y = - \frac{ \sqrt{2} } {2} , gives us x+y=0,x2+y2=1,x3+y3=0 x+y = 0, x^2 + y^2 = 1, x^3 + y^3 = 0 but x4+y4=12x^4 + y^4 = \frac{1}{2} (and the higher even powers clearly do not yield integers).

Calvin Lin Staff - 7 years, 3 months ago

Log in to reply

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

Ivan Koswara - 7 years, 3 months ago

Log in to reply

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

2xy=(x+y)2(x2+y2)N. 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 - 7 years, 3 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

Victor Loh - 7 years, 3 months ago

This was my method!

Wei Jie Tan - 7 years, 3 months ago

I would greatly appreciate help too.

I am serious.

Yuxuan Seah - 7 years, 3 months ago

Log in to reply

You are totally 44

Wei Jie Tan - 7 years, 3 months ago

Log in to reply

you are totally 18

Victor Loh - 7 years, 3 months ago

Log in to reply

@Victor Loh You are totally 14

Wei Jie Tan - 7 years, 3 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 - 7 years, 3 months ago

Log in to reply

@Yuxuan Seah 13.

Wei Jie Tan - 7 years, 3 months ago

We use the identity xn+yn=(x+y)(xn1+yn1)xy(xn2+yn2)x^n+y^n=(x+y)(x^{n-1}+y^{n-1})-xy(x^{n-2}+y^{n-2}).

First we prove that xyxy is an integer. Note that 2xy=(x+y)2(x2+y2)Z2xy=(x+y)^2-(x^2+y^2)\in \mathbb{Z} and 2x2y2=(x2+y2)2(x4+y4)Z2x^2y^2=(x^2+y^2)^2-(x^4+y^4)\in \mathbb{Z}. From the first equation we see that 2xy=m2xy=m for some integer mm, so xy=m2xy=\frac{m}{2}. From the second equation we have 2x2y2=n2x^2y^2=n for some integer nn. Plugging xy=m2xy=\frac{m}{2} yields 2(m24)=nm22=nZ2\left(\frac{m^2}{4}\right)=n\Leftrightarrow \frac{m^2}{2}=n\in \mathbb{Z}. So 2m2\mid m. Hence xy=m2Zxy=\frac{m}{2}\in \mathbb{Z}, as desired. //

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

Arkan Megraoui - 7 years, 2 months ago

STATE YOUR SOURCE

Wei Jie Tan - 7 years, 3 months ago
×

Problem Loading...

Note Loading...

Set Loading...