Question

If n and 6 are coprime numbers, prove that n^2 - 1 is divisible by 24.

Answer 1

I got just as far as to write n^2 - 1 = 24 * k

Answer 2

in trhis case n=6+/-1 so n=5 and/or 7

for 5 will get 25-1=24 what is divisidle by 24
for 7 ----- 49-1=48=24*2 ------- 24

Answer 3

@jhonyy9 I need more universal proof. :/

Answer 4

i thought it on complet induction proof method

6=3*2
5=3*2-1
7=3*2+1

use for this 6n and 6n +/- 1

Answer 5

for 5 and 7 this is true like above wrote

so suppose for n=k is true

and rewrite it and proove it for (k+1)

Answer 6

for 6n will be n^2 -1 so (6n)^2 -1 = (6n-1)(6n+1)

for case of 6n-1 will result (6n-1)^2 -1 = (6n)^2 -12n +1
and for 6n+1 ------- (6n+1)^2 -1 = (6n)^2 +12n +1

Answer 7

Step1

Consider the remainders when 'n' is divided by 6

Answer 8

5,4,3,2,1

Answer 9

What remainders are possible ?
Keep in mind the given fact : n and 6 are coprime

Answer 10

So, the possible remainders are 5, 4, 3, 2, and 1.

Answer 11

Really sure the remainders 2,3,4 are valid ?

Answer 12

Oh, you are right! So, they are 5, and 1.

Answer 13

Why ?
I'd like to see your explanation for excluding 2,3,4,0

Answer 14

So, 6 can be divided by 2, 3. To get remainder 2, we need to have number of form 6k + 2; n would need to be 6k+2, but n and 6 are coprime and 6k+2 = 2(3k +1)
Same goes for 3 and 0.
Not really sure about 4 :/

Answer 15

Nice.

Is it hard to see that
n and 6
are not coprime when n = 6k+4 ?

Answer 16

Yes, just noticed. 6k+4 = 2(3k + 2) and that means 6 and n would have divisor 2.

Answer 17

Good. Let's move to step2

Answer 18

Before that notice this
In modulus 6, the remainders 5 and -1 are sane

Answer 19

Yes, I know that.

Answer 20

So we can say that the only possible remainders when n is divided by 6 are +-1

Answer 21

Yes.

Answer 22

So, what would be the second step? ;)

Answer 23

Step2
Let \(n = 6k \pm 1\)
Then we need to show that \(( 6k \pm 1)^{2}-1\) is divisible by 24

Answer 24

36k^2 +/- 12k + 1 - 1 = 24q
36k^2 + / - 12k = 24q
3k^2 + / - k = 2q

Answer 25

Oh, did one step too far.
But how would 36k^2 + / - 12k prove 24q?

Answer 26

12(3k^2 + / - k) = 24q
3k^2 + / - k = 2q

Still need to prove that left side is divisible by 2.

Answer 27

Looks great!
Factor 3k^2 + / - k
Then stare at it

Answer 28

Hm... k(3k + / - 1) seems similar to n = 6k +/ - 1; n + / - 1 = 6k; k((n + / - 1)/2 + / - 1)
Is that right?

Answer 29

\(3k^2 \pm k = 2k^2 + k^2 + k = 2k^2 + k(k+ 1) \)

Answer 30

How comes that after the equal sign the k got rid of + / -?

Answer 31

Notice that \(2k^2\) is divisible by 2
What can you say about the expression \(k(k+1)\) ?

Answer 32

Oh sorry, that was a typo.
Just put that - sign also

Answer 33

Its going to be even! Consecutive numbers multiplied by each other give out even product. Oh my!
Even + even = even and even is divisible by 2.

Answer 34

That'll do

Answer 35

Amazing! I think that I would never get to the solution by myself ;) Thank you VERY much! :)

Answer 36

Np, yw :)