Proving the Divisibility of 5^n by 4

[cscott]

Show that 5^n is divisible by 4 (ie. prove $5^n = 4x$)

The case for n = 1 works

For n = k + 1

$$5^{k+1} - 1 = 4x$$
$$5^k \cdot 5 - 1 = 4x$$

Then I can only see doing:
$$5(5^k - 1 + 1) - 1 = 4x$$
and substituting in the case for n = k
$$5(4x + 1) - 1 = 4x$$

But it doesn't work out...

 

[Muzza]

Of course it doesn't work out, you've used x to mean two different things.

Assume that there exists an x such that 5^k - 1 = 4x.

You then wish to FIND an y such that 5^(k + 1) - 1 = 4y (or at least prove that such a y exists).

It's not necessarily the case that x = y.

 

[shmoe]

$$5^{k+1} - 1 = 4x$$
...
and substituting in the case for n = k
$$5(4x + 1) - 1 = 4x$$

On one hand you're saying $$5^{k+1}-1=4x$$, then you're substituting $$5^{k}-1=4x$$? Both these statements are true for any natural number k, but for different values of $$x$$ in each.

Suggestion-don't start with what you're trying to prove, just begin with $$5^{k+1}-1$$ and manipulate it until you get something divisible by 4.

 

[cscott]

I can only manipulate it so far... if I eventually substitute the 4x in I will end up with 20x + 4 (LHS) which is divisible by 4. Is this correct?

If the RHS was 4y instead I'd end up with 5x + 1 = y

If I'm wrong, how do I get past $5^k \cdot 5 - 1$

 

[shmoe]

I can only manipulate it so far... if I eventually substitute the 4x in I will end up with 20x + 4 (LHS) which is divisible by 4. Is this correct?

Exactly, that's all there is to it.

 

[cscott]

Thanks a lot!