Browse · MathNet
PrintIrska
Ireland number theory
Problem
For any positive integer define Find the greatest common divisor of , , , \ldots .
Solution
Let be the g.c.d. of . Since , it follows that any prime divisor of is less than or equal to . Let be a prime number such that . Since , it follows that . Observe that are relatively prime to . so (and thus ) is divisible by but not by . We have thus proved that is not divisible by the square of any prime number.
Since , it follows that divides the product of all prime numbers less than or equal to , that is, .
To show that it is enough to prove that for all , the number is divisible by .
Let . Then, one of the numbers or is divisible by , so . Similarly, one of the numbers is divisible by so . Then, one of the numbers is divisible by which yields . In the same manner we obtain and . Therefore is a multiple of and so, the g.c.d. is .
Since , it follows that divides the product of all prime numbers less than or equal to , that is, .
To show that it is enough to prove that for all , the number is divisible by .
Let . Then, one of the numbers or is divisible by , so . Similarly, one of the numbers is divisible by so . Then, one of the numbers is divisible by which yields . In the same manner we obtain and . Therefore is a multiple of and so, the g.c.d. is .
Final answer
2310
Techniques
Greatest common divisors (gcd)Inverses mod n