Algebra: Factoring (a^n - b^n)

Now that finals are over, I can resume serious work on this project.

I moved to the Algebra section of Putnam & Beyond, because I was now interested in something more than heuristics.

Something that comes up very often in contest problems is the factorization of a^n-1 and a^n+1.

It is easy to see that a^n -1= (a-1)(1+ a + ...a^(n-1))

And similarly, if n is odd, a^n + 1 =(a+1)(1 - a +a^2 - ... +a^(n-1)).

If n=q*p, we can replace a with a^p or a^q, to get some different identities.

So we basically get that if p divides n, then a^p -1 divides a^n - 1.

Looking at this from a number theoretic perspective, we have the following result:

Theorem: Lifting Exponent Lemma

vp(x^n-y^n)=vp(x-y)+vp(n)
For x,y, integers such that p does not divide x or y, but divides x-y.

vp(x) is called the p-adic valuation of x, and is the largest k such that p^k divides x.
(e.g. v3(18)=2)

The proof of this theorem is a bit complicated, and I will not include it here.

Also, the solutions to most of these problems are not really supposed to involve this theorem, but it is a result I know, so I will use it.


Problem:
Show that for an odd integer n ≥ 5,
(nC0)5^(n-1)-(nC1)5^(n-2)+(nC2)5^(n-3)....+(nCn-1)
is not a prime number.

Recall that (a+b)^n=(nC0)a^n + (nC1)(b(a^(n-1)) +... (nCn)b^n.

Thus our expression is equivalent to:

(((5-1)^n)/5)+(1/5)=(4^n+1)/5

So we now just need to show (4^n+1)/5 is not prime.

For any n>5, pick some p dividing n. By Lifting the Exponent, vp(4^n+1)=vp(5)+vp(n)>0.
So, p|(4^n +1), and, since p is not 5, dividing by 5 does not change this fact.
(If p is 5, then we have v5(5)+v5(n)>1, so when we divide by 5, we reduce the exponent of 5 by 1, so we still get something nonzero)

So if p divides n, p divides (4^n+1)/5, to show (4^n+1)/5, we need to show it must have another divisor, however this is obvious, as (4^n+1)/5 > n>=p, so (4^n+1)/5 is not equal to p, and thus must have another divisor.


Problem: Let a and b be coprime integers greater than 1. Prove that for no n ≥ 0 is a^2n +b^2n
divisible by a + b.

Note that (a+b) divides a^2n-b^2n. (a^n-b^n)(a^n+b^n), if n is even, then (a^2-b^2) divides (a^n-b^n), and (a+b) divides (a^2 - b^2). If n is odd, then (a+b) divides (a^n+b^n).

Assume for the sake of contradiction that  for some n, a^2n +b^2n is
divisible by a + b.

Since (a+b) also divides a^2n-b^2n, it divides their difference, 2b^2n.

However, this is impossible, as (a+b) is coprime to b, so we must have (a+b)=2, which cannot happen as a,b>1!