hello,

Using modular arithmetic how could you show that 42 divides n⁷ - n for all n. I know that you have to factorise n⁷ - n, i.e. to n(n-1)(n+1)etc... but then I don't understand the concept!

Thank you

Not for n=0,1, and various negative numbers.

This is the same as proving:

mod 7 is immediate from Fermat's Little Theorem.

mod 2 is trivial

mod 3 requires a bit of thinking. From Fermat's Little Theorem , n³ º n, so n³ º n³×n³×n º n³ º n.

Hence 42 divides n⁷ -n for all integer n (there
are no exceptions).

Kerwin

For mod 3 you can also sub in -1,0,1. Then note that all numbers can be written as one of the following:

-1 + 3k
0 + 3k
1 + 3k

where k is an integer. Then just use the binomial expansion to show each of these satisfies the requirement: n^7 - n is a multiple of 3.

I think that it could be making things unnecessarily confusing using mods here.

How can you factorise out n⁷ - n?

Well n⁷ - n = n(n⁶ - 1) = n(n³ - 1)(n³ + 1)
= n(n-1)(n² + n + 1)(n + 1)(n² - n + 1).

So that gives you the factors of 3 and 2 straight away. (i.e. n-1,n,n+1 are three consecutive numbers, so one must have a factor of three and one must have a factor of 2).

However, what about the factor of 7? Well, I think I will leave that to someone else to explain or you to work out, as I have to go now..

Yes that's very true; and once you've got to:

n⁷ - n = n(n³ - 1)(n³ + 1) = n(n-1)(n² + n + 1)(n + 1)(n² - n + 1)

You can then write:

n² + n + 1 = (n + 3)(n - 2) + 7
n² - n + 1 = (n + 2)(n - 3) + 7

So:

n⁷ - n = n(n - 1)[(n + 3)(n - 2) + 7](n+1)[(n + 2)(n - 3) + 7]

We also know:

[(n + 3)(n - 2) + 7][(n + 2)(n - 3) + 7]
= (n - 3)(n - 2)(n + 2)(n + 3) + 7[(n + 3)(n - 2) + (n + 2)(n - 3)] + 49

So n⁷ - n = (n - 3)(n - 2)(n - 1)n(n + 1)(n + 2)(n + 3) + 7n(n - 1)(n + 1)[(n + 3)(n - 2) + (n + 2)(n - 3) + 7]

The first term is the product of 7 consecutive integers (so is a multiple of 7). And the second is a multiple of 7 by virtue of the 7 outside the brackets. Therefore it is a multiple of 7.

As Kerwin says, that n⁷ - n is a multiple of 7 is part of a more general result (called Fermat's little theorem) which states:

n^p - n

is a multiple of p (for all prime p and all integers n).

Although Michael's proof is very nice and doesn't involve modular arithmetic, we can prove the result of mod 7 by some fairly simple modular arithmetic not involving FLT. (I'm probably overcomplicating things though)


First

n⁷ -n = n(n-1)(a² +a+1)(a+1)(a² -a+1)

And because,

n²+n+1=(n²+n-6)+7 º a²+a-6=(n-2)(n+3) (mod 7)

[can you see why?]

And since( using essentially the same factorization as before),

Looking back at my proof, I've just noticed that it nearly identical to Michael's, except mine uses mods, which was what we were trying to avoid in the first place!

Sorry if my explanation has just confused,

Brad