help please
prove that if n natural , 2 does not divide n ,3 does not divide n
then 24 divides n^2 -1
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 n^{2} is congruent to 1 mod 24. So any natural number n prime to 24 is congruent to one of these and you're done.
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 n^{2} - 1 = (3m + 1)^{2} - 1 = 9m^{2} + 6m + 1 - 1 = 3(3m^{2} + 2), which is divisible by 3.
Case 2: n = 3m + 2.
Then n^{2} - 1 = (3m + 2)^{2} - 1 = 9m^{2} + 12m + 4 - 1 = 3(3m^{2} + 4m + 1), also divisible by 3.
So in all cases, we have n^{2} - 1 is divisible by 3.
Almost there: we now need to show that 8 divides n^{2} - 1, and since gcd(3,8) = 1, this will show 24 divides n^{2} - 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 n^{2} - 1 is a multiple of 4, and the other is even, their product is a multiple of 8. Thus 8 divides n^{2} - 1, and we are done.