DIVISIBILITY CONGRUENCE question

  • Context: Undergrad 
  • Thread starter Thread starter mathmajor2013
  • Start date Start date
  • Tags Tags
    Divisibility
Click For Summary
SUMMARY

If gcd(a, 42) = 1, then a^6 - 1 is divisible by 168. The proof involves demonstrating the divisibility of a^6 - 1 by the prime factors of 168, specifically 3, 7, and 8. Utilizing Fermat's Little Theorem, the divisibility by 3 and 7 can be established. For the divisibility by 8, the expression a^6 - 1 can be factored to facilitate the proof.

PREREQUISITES
  • Understanding of gcd (greatest common divisor) and its properties
  • Fermat's Little Theorem and its application to modular arithmetic
  • Factoring polynomials, specifically a^6 - 1
  • Basic knowledge of divisibility rules and prime factorization
NEXT STEPS
  • Study the application of Fermat's Little Theorem in modular arithmetic
  • Learn about polynomial factorization techniques, particularly for expressions like a^n - b^n
  • Research the properties of gcd and its implications in number theory
  • Explore advanced divisibility rules and their proofs in number theory
USEFUL FOR

Mathematicians, students studying number theory, and anyone interested in modular arithmetic and divisibility proofs.

mathmajor2013
Messages
26
Reaction score
0
Question: If gcd(a,42)=1, show that a^6 - 1 is divisible by 168.

Answer: So I know that if 42 were prime, than the Little Fermat Thm says that a^p-1 is congruent to 1 mod p. But I have no idea where to start if p is not prime. Help please.
 
Physics news on Phys.org
prove the divisibility by 3, 7 and 8 separately. 3 and 7 can be done with Little Fermat's theorem.
For divisibility by 8, factor a^6 -1.
 

Similar threads

Undergrad Trouble understanding an online solution to an exercise in Dummit & Foote
  • · Replies 21 ·
Replies
21
Views
2K
Undergrad Congruence for Symmetric and non-Symmetric Matrices for Quadratic Form
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Questions about non existence of GCDs vs (coimages, cokernels)
  • · Replies 12 ·
Replies
12
Views
1K
Graduate Odd Prime Triples: Find & Explore Solutions!
  • · Replies 2 ·
Replies
2
Views
4K
Graduate How to Prove a Congruence in Modulo pq with Distinct Primes?
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Another Question about Finite Dimensional Division Algebras ....
  • · Replies 14 ·
Replies
14
Views
2K
Undergrad Prime number dividing fractions.
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad N-Dimensional Real Division Algebras
  • · Replies 6 ·
Replies
6
Views
2K
Graduate Primitive roots & Reduced residue system
  • · Replies 8 ·
Replies
8
Views
8K
Undergrad Meaning of "passage to the quotient"?
  • · Replies 3 ·
Replies
3
Views
2K