1. ## divisibility

prove that if n natural , 2 does not divide n ,3 does not divide n

then 24 divides n^2 -1

2. ## Re: divisibility

Hi,
The problem is easy if you know about the multiplicative group of integers mod 24. See Multiplicative group of integers modulo n - Wikipedia, the free encyclopedia.

Alternatively, for n less than 24, n=1, 5, 7, 11, 13, 17, 19 or 23 are the values prime to 24. By direct calculation each of these satisfy n2 is congruent to 1 mod 24. So any natural number n prime to 24 is congruent to one of these and you're done.

3. ## Re: divisibility

A slightly less abstract formulation than johng's:

if 3 does not divide n, then n = 3m + 1, or 3m + 2 for some integer m.

Case 1: n = 3m + 1.

Then n2 - 1 = (3m + 1)2 - 1 = 9m2 + 6m + 1 - 1 = 3(3m2 + 2), which is divisible by 3.

Case 2: n = 3m + 2.

Then n2 - 1 = (3m + 2)2 - 1 = 9m2 + 12m + 4 - 1 = 3(3m2 + 4m + 1), also divisible by 3.

So in all cases, we have n2 - 1 is divisible by 3.

Almost there: we now need to show that 8 divides n2 - 1, and since gcd(3,8) = 1, this will show 24 divides n2 - 1.

Now since 2 does not divide n, n is odd. Thus n - 1 and n + 1 are both even. One of these must be divisible by 4:

If n - 1 is not divisible by 4, since it is even, it must be of the form n - 1 = 4k + 2. In that case, n + 1 = n - 1 + 2 = 4k + 2 + 2 = 4(k + 1).

Since one factor of n2 - 1 is a multiple of 4, and the other is even, their product is a multiple of 8. Thus 8 divides n2 - 1, and we are done.