Theorem I:
a^n+b^n = (a+b)(a^(n-1) - a^(n-2)b +...+b^n-1)
So a+b divides a^n+b^n

Theorem 1     8 divides (8x+3)^m + (8y+5)^n for integers x,y, m,n, m,n odd.

Corollary 1    8 divides 3^m+ 5^n  for odd m,n
Proof:

Let 5 = 4+1.
Using the binomial expansion for
(a+b)^n=a^n+n!/1!(n-1)!a^(n-1)b+n!/2!(n-2)!a^(n-2)b^2+...+n!/(n-1)!ab+b^n
we have

(1)     (4+1)^n=4^n+n!/1!(n-1)!4^3+n!/2!(n-2)!4^2+...+4n+1
Since n is odd by definition, (1) is of the form 4(2h+1)+1. Now 3^m + 4(2k+1)+1 = 3^m+1 + 4(2h+1). By expanding using Theorem I, 3^m+1 is divisible by 3+1 = 4. Moreover, since n is odd there is an even number of terms containing a power of 3 in Theorem I making the expansion (a^(n-1) - a^(n-2)b +...+b^n-1) odd for a=3,b=1. So 3^m+1 = 4(2j+1). Then 4(2j+1) + 4(2h+1) = 4(2(j+h)+2) = 8z  for some z as desired.

Now the binomial expansion of (8x+3)^m + (8y+5)^n will yield 8w + 3^m+5^n for some integer w. Then by corollary 1, (8x+3)^m + (8y+5)^n is divisible by 8.
 

It now  remains to prove theorem I.

 a^n+b^n = (a+b)(a^(n-1) - a^(n-2)b +...+b^n-1)

Multiplying out the right side by a and  b and adding  we have,

a^n - a^(n-1)b +a^(n-2)b^2+ . . . + ab^(n-1) +

       +a^(n-1)b - a^(n-2)b^2+ . . . + b^n

The central terms obligingly cancel and we are left with a^n + b^n as desired.

Also proof from CTK discussion.

Subject: "RE: 8 divides (8x+3)^m + (8y+5)^n"

Hi Sfwc, Thank for taking interest in my "discovery." >For a quick proof, work mod 8 (I think modular arithmetic is >explained somewhere in CTK, if you are'nt familiar with it, >but I'm not entirely sure where) I am familiar with it but do not understand it fully and probably never will. I try to avoid it with my "forms" method which I guess is congruent to it. I have always had trouble with this congruent business and I would wager I am not alone. It is vague to say in the least and unless you are a teacher, who rattles it off every day, you have to re-learn the damn thing after you haven't used it in a while - kinda like assembly, C and far worse C++ languages -fancy footwork of the experts. Congruences have their place but not for the man in the street. If you can't explain it to the man in the street then it will not stand the test of time. What good is Wiles proof on Fermat's last theorem? Who in the heck understands it even in outline? Relativity is subtle and complex but at least most people get the idea. You can have far more success teaching the man on the street integral calculus than residue classs and modular arithmetic. Diaphantine equations? Yes he would understand these. Sure a congruent b mod m <=> (implies and is implied by) m divides a-b is the definition and from this definition we can draw a number of theorems which you use below. Also I want to point out to anyone else who doesn't fully understand congruences,residues, etc that the "=" sign in your "short proof" below both means equality and congruence. Eg., 3^2 = 9 while 9 = 1 mod 8 the = means congruent to or the same form as or equivelant to etc. Below I annotate what I understand in your proof. I will use the tilde ~ to signify congruence and the bar | to signify divides => to mean implies. > >We know 3^2 = 9 = 1 mod 8 and 5^2 = 25 = 1 mod 8 Yes. 8 | 9-1 and 8 | 25-1 and 8 | 9*2 - 2 and 25*3 - 3. Looks like a pattern here. If a ~ 1 mod m then ax ~ 1x mod m. This is evident when we observe from the definition m | ax - x = x(a-1) Now if a ~ 1 mod 8 then a^y ~ 1 mod 8. This follows if we repeat the pattern above since m | ax^y - x^y = x^y(a-1). Similarly, a ~ b mod m and c ~ d mod m => a +c ~ b +d mod m. This becomes evident when we apply the definition m | a +c - (b +d) because m | (a-b) and m | (c-d) => m | a +c - (b +d) => a +c ~ (b +d) mod m. >Let m = 2a+1 >Let n = 2b+1 Normal equality here. > >(8x +3)^m (8y +5)^n = 3^(2a +1) 5^(2b +1) Looks like this = is ~. From a forms stand point, the binomial expansion will yield (8x +3)^m (8y +5)^n = 8K +8J 3^(2a +1) 5^(2b +1) for some integers K,J. So it is a matter of showing 3^(2a +1) +5^(2b +1) is divisible by 8 to prove the assertion. I am with you so far. > = (3^2)^a * 3 (5^2)^b * 5 This is some laws of exponents. Still with you. > = 3 * 1^a +5 * 1^b Here I am lost. 9^a is the same form as 1, 25^b same form as 1? I know this from the remarks above. 9 ~ 1 mod 8 25 ~ 1 mod 8 9^a ~ 1 mod 8 25^b ~ 1 mod 8 3*9^a ~ 3 mod 8 5*25^b ~ 5 mod 8 implies 3*9^a +5*25^b ~ (3 +5) mod 8 So 8 divides 3^(2a +1) +5^(2b +1) > = 3 +5 > = 8 = 0 mod 8 >as required > >PS alexb, this board seems to lose plus signs when posting. >I hope this can be sorted out as it could get confusing. You can cheat this flaw by turning off the emoticons and placing a space between your arguments but with the +juxtaposed (as here) next to the following argument. This flaw is not much worse than the dumb wordwrapping requirement to make the text neat as is the case in most of the list editors out there,eg., yahoo,hotmail,scimath,sloan's etc. Boggles my mind why this can't be fixed. I guess it is like the manual typewriter; you have to carriage return when you want to go to the next line. Have fun in the facinating world of numbers. Cino

Cino Hilliard