Skip to main content
OlympiadHQ

Browse · MathNet

Print

Irska

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 .
Final answer
2310

Techniques

Greatest common divisors (gcd)Inverses mod n