equation and her solutions...

• Jan 29th 2013, 12:48 PM
darence
equation and her solutions...
If a and b are solutions of equation $\displaystyle x^2-6x+1=0$, proove that $\displaystyle \forall n \in N$ number $\displaystyle a^n+b^n$ is integer not divisible with 5.

• Jan 29th 2013, 02:29 PM
Deveno
Re: equation and her solutions...
since x2 - 6x + 1 = (x - a)(x - b) = x2 - (a+b)x + ab,

we have a + b = 6, which is clearly an integer. note 5 does not divide 6. note also that ab = 1, as we will need this later.

also (a + b)2 = (a + b)(a + b) - 2ab = 36 - 2 = 34, which is also an integer.

now let's prove an + bn is an integer, by induction on n.

suppose ak-1 + bk-1 is an integer, for all k < n as our induction hypothesis.

then an + bn = (an-1 + bn-1)(a + b) - (ab)(ak-2 + bk-2)

since the RHS side is all integers, the LHS must be, as well.
• Jan 29th 2013, 02:36 PM
emakarov
Re: equation and her solutions...
Yes, but the question is about $\displaystyle a^n + b^n$ and not $\displaystyle (a+b)^n$.
• Jan 29th 2013, 02:53 PM
Deveno
Re: equation and her solutions...
Quote:

Originally Posted by emakarov
Yes, but the question is about $\displaystyle a^n + b^n$ and not $\displaystyle (a+b)^n$.

its funny how your mind plays tricks on you. i noticed this just as i posted my answer, and amended it accordingly.
• Jan 29th 2013, 03:42 PM
darence
Re: equation and her solutions...
thank you very much.
How to proove a^n+b^n is not divisible with 5?
• Jan 29th 2013, 03:43 PM
emakarov
Re: equation and her solutions...
Quote:

Originally Posted by Deveno
an + bn = (an-1 + bn-1)(a + b) - (ab)(ak-2 + bk-2)

And concerning divisibility by 5, it is sufficient to consider this recurrence relation modulo 5: this is a periodic sequence.

Quote:

Originally Posted by Deveno
its funny how your mind plays tricks on you.

I can relate. On the other forum, there was a discussion about formal proofs. I argued that verifying proofs on the computer ensures their correctness for all practical purposes, but agreed that there is no absolutely 100% guarantee, if only for this reason. Though typos can usually be eliminated by a community of researchers.