Prove that 12 | n^2-1 if g.c.d. (n,6)= 1.

  • Thread starter Fisicks
  • Start date
In summary, using Fermat's Little Theorem and the property of greatest common divisors (gcd), it can be proven that if gcd(n,6)=1, then 12 | n^2-1. This can be shown by breaking down n^2-1 into (n-1)(n+1) and using the properties of even and odd numbers to show that 4 and 3 both divide (n-1)(n+1), thus resulting in 12 dividing (n-1)(n+1). This provides an elegant and simple proof for the given statement.
  • #1
Fisicks
85
0
Prove that 12 | n^2-1 if g.c.d. (n,6)= 1.

I'm pretty sure i already proved this using fermats little theorem, 3 | n^2-1 and 2| n-1, and since n^2-1 is always greater than or equal to 24, (cept for n=1 in which case any number dividies into 0) therefore since 12=2*2*3, 12 | n^2-1

This isn't really atheistically pleasing, can anyone do this a different way?
 
Last edited:
Physics news on Phys.org
  • #2


hi there

n^2-1 = (n-1)(n+1)
gcd(n,6)=1 implies n is odd, so n-1 is even and n+1 is even, thus 4|(n-1)(n+1)
gcd(n,6)=1 implies: either n=1 mod 3 (in which case n-1 = 0 mod 3)
or n=2 mod 3 (in which case n+1 = 0 mod 3),
in both cases 3|(n-1)(n+1)
From 4|(n-1)(n+1) and 3|(n-1)(n+1) we conclude that 12|(n-1)(n+1)
 
  • #3


i followed your proof up to the congruence part, I am new to this, and that's very simple and clever, i like it.
 
  • #4


I don't have my own proof for this, but what Liwuinan said is right (as far as I can tell anyway). I loved the elegance of it. Simple and sweet, just like a proof should be
 
  • #5


thank you guys for a nice welcome to this forum! :)
 

FAQ: Prove that 12 | n^2-1 if g.c.d. (n,6)= 1.

1. What does "12 | n^2-1" mean?

This notation means that 12 is a factor of the expression n^2-1, or in other words, n^2-1 is a multiple of 12.

2. What does "g.c.d. (n,6)= 1" mean?

The notation "g.c.d." stands for "greatest common divisor". So, this statement means that the greatest common divisor of n and 6 is 1, indicating that n and 6 are relatively prime.

3. Why is it important for n and 6 to be relatively prime?

If n and 6 are relatively prime, it means they do not share any common factors besides 1. This is important because it simplifies the proof and allows us to focus on the relationship between 12 and n^2-1 without any other complicating factors.

4. How do you prove that 12 | n^2-1 if g.c.d. (n,6)= 1?

To prove this statement, you can use the fact that if a and b are relatively prime, then a | (b*c) if and only if a | c. In this case, we can set a=12, b=n, and c=n+1. Since 12 and n are relatively prime, we know that 12 | n+1 if and only if 12 | (n+1)-n, which simplifies to 12 | 1. Since 12 is a factor of 1, the statement is true.

5. Can you provide an example to illustrate this proof?

Sure, let's take n=5. Since n=5 and 6 are relatively prime (g.c.d. (5,6)=1), we know that 12 | 5^2-1. Plugging in n=5, we get 5^2-1=24, and since 24 is a multiple of 12, the statement is true. This example also shows that the proof works for any value of n that is relatively prime to 6.

Similar threads

I Proving inequality about dimension of quotient vector spaces
Replies
0
Views
363
I I think I've hit upon a very easy proof of impossibility of quintic
Replies
2
Views
1K
MHB Is \( n! > 2^n \) for \( n \ge 4 \)?
Replies
4
Views
1K
Deduce that ## 13\mid (11^{12n+6}+1) ##
Replies
2
Views
771
MHB If 2 columns are identical is there infinite solutions
Replies
4
Views
2K
Solution of a certain NxN matrix, when N->∞
Replies
2
Views
1K
I Fundamental representation and adjoint representation
Replies
27
Views
2K
Find the values of ## n\geq 1 ## for which ## 1+2+3+\dotsb +n ##.
Replies
4
Views
956
Proving that ##\lim [\sqrt{4n^2 +n} - 2n] = \frac{1}{4}##
Replies
9
Views
2K
MHB Equivalent Norms: Proving $\|A\| \leq \|A\|_{Eucl} \leq \sqrt{n}\|A\|$
Replies
4
Views
1K

Hot Threads

Recent Insights

Back
Top