Division of Integers: Show n33-n Divisible by 15

[beetle2]

Homework Statement

Show that for every integer n the number n³³ - n is divisible by 15

Homework Equations

The Attempt at a Solution

Not sure what to do.

I was thinking it might have something to do with both numbers are divisable by 3

ie the power = 3 x 11 and the divisor = 3 x 5 as with all intgers they are products of prime numbers.

(n³)¹¹-n | (2x3)+3²

any help greatly appreciated

 

[Mark44]

Homework Statement

Show that for every integer n the number n³³ - n is divisible by 15

Homework Equations

The Attempt at a Solution

Not sure what to do.

I was thinking it might have something to do with both numbers are divisable by 3

If n³³ - n is divisible by 15, it must be divisible by 3 and by 5.
n³³ - n = n(n³² - 1)

Continue with the factorization that I started until you have it down to irreducible factors. It's pretty easy to show that the expression is divisible by 3, which you can tell from three of the factors you end up with. (There are quite a few more.)

It's a little more involved to show that the expression is also divisible by 5, but if you look at the possible values for n modulo 5, you'll find that there is one factor that is also divisible by 5. I found it helpful to make a table with all the factors across the top, and the five possible values of n (mod 5) down the side.

ie the power = 3 x 11 and the divisor = 3 x 5 as with all intgers they are products of prime numbers.

(n³)¹¹-n | (2x3)+3²

any help greatly appreciated

 

[beetle2]

These are the factors.

(x - 1) x (x + 1) (x² + 1) (x⁴ + 1) (x⁸ + 1) (x¹⁶ + 1)


Do i have to reduce these to irreducible polynomials mod 15 ?

 

[Mark44]

They should be in terms of n, since that's how the problem is stated. These factors are all you need, plus the idea that if m = a (mod c) and n = b (mod c), then mn = ab (mod c).

First show that the product is divisible by 3. You should be able to do that with the first three factors that you show. Any number n is going to fall into one of three congruence classes: 0, 1, or 2. If n = 0 (mod 3), then clearly the product is divisible by 3. If n = 1 (mod 3), what can you say about the other factors? If n = 2 (mod 3), what can you say about the other factors?

Next, show that the product is divisible by 5. Any number n will fall into one of five different congruence classes. Do the same kind of analysis as above to show that whatever value n is, one of the factors you have is divisible by 5..

 

[beetle2]

((n-1)*(n+1)*(n^2+1)=0 mod 3 when n = 2

((n-1)*(n+1)*(n^2+1)=0 mod 3 when n = 1


((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 1

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 2

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 3

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 4

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 6

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 7

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 8

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 9

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 11

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 12

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 13

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 14


Using what you said if m = a (mod 5) and n = b (mod 5), then mn = ab (mod c).

I chose m= 11 = a = 12 mod 5 and n = 8 = b = 9 mod 5

then

mn = ab (mod 5).

88 = 108 = 3 mod 5

How does that relate to the mod 3's?

 

[Mark44]

((n-1)*(n+1)*(n^2+1)=0 mod 3 when n = 2

((n-1)*(n+1)*(n^2+1)=0 mod 3 when n = 1

Three of the factors are n - 1, n, and n + 1, right? That's three integers in succession. Whenever you have any three successive integers, one of them will be a multiple of 3.

Take any integer value of n. Exactly one of the following must be true:
n \equiv 0 (mod 3)
n \equiv 1 (mod 3)
n \equiv 2 (mod 3)

For each of these three cases, which one of n - 1, n, or n + 1 will be divisible by 3?

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 1

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 2

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 3

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 4

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 6

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 7

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 8

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 9

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 11

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 12

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 13

((n-1)*(n+1)*(n^2+1)*(n^4+1)*(n^8+1)*(n^16+1)) = 0 mod 5 when n = 14


Using what you said if m = a (mod 5) and n = b (mod 5), then mn = ab (mod c).

I chose m= 11 = a = 12 mod 5 and n = 8 = b = 9 mod 5

?
Instead of showing that the big expression is divisibly by 15, it's easier to show that it is divisible by 3 and it is divisible by 5. You just need to be a little careful that if one of the factors is divisible by 3, then either it is also divisible by 5 or one of the other factors is divisible by 5.

For example, if n \equiv 0 (mod 5), then n would be in the set {0, 5, 10, 15, 20, 25, 30, ...}. All of these numbers are divisible by 5, and every third one is also divisible by 3. If n is one of the numbers not divisible by 3 (e.g., 5, 10, 20, 25, etc.), then either n + 1 is divisible by 3 or n - 1 is divisible by 3.

Do this for the other four possibilities for n (mod 5).

then

mn = ab (mod 5).

88 = 108 = 3 mod 5

How does that relate to the mod 3's?