For any positive integer $n$, we define the integer $P(n)$ by : $P(n)=n(n+1)(2n+1)(3n+1)...(16n+1)$. Find the greatest common divisor of the integers $P(1)$, $P(2)$, $P(3),...,P(2016)$.
Problem
Source: PAMO 2016
Tags: number theory, Integer Polynomial, greatest common divisor
mszew
29.04.2016 22:38
Here comes some hints/steps:
$GCD | P(1)=17!$
$GCD=2^a \times 3^b \times 5^c \times 7^d \times 11^e \times 13^f \times 17^g$
Notice that $P(2)=2 \times 3 \times 5 \times \dots \times 33$ is multiple of $2$ but not $2^2$ similarly for every prime $p$, we have $P(p)$ multiple of $p$ but all the $ip+1$ factors are not so $1$ is the max prime power of each prime on GCD
for a prime $p$ for every $n$ natural either $p|n$ or
one of the numbers $n+1$, $2n+1$, ..., $(p-1)n+1$, $pn+1$ is divisible by $p$
For all primes $p<16$ we have that $p| P(n)$
for a prime $p>2$ for every $n$ natural either $p|n$ or
one of the numbers $n$, $n+1$, $2n+1$, ..., $(p-1)n+1$ is divisible by $p$
Proof: assume that there is no number divisible by $p$ then from those $1+p-1=p$ numbers there are $2$ with the same remainder mod $p$ the difference between them is multiple by $p$ and of the form either $1$, $in+1$ or $in$ for $0<i<p-1$ contradiction
$17| P(n)$
$GCD=2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17$
aopser123
30.04.2016 02:23
Can't find better place to ask, but what is PAMO?
shinichiman
30.04.2016 02:26
aopser123 wrote: Can't find better place to ask, but what is PAMO? It's Pan-African Mathematical Olympiad.
aopser123
30.04.2016 02:27
shinichiman wrote: aopser123 wrote: Can't find better place to ask, but what is PAMO? It's Pan-African Mathematical Olympiad. Oh, thanks!
khalilmiri
01.06.2016 14:47
mszew wrote: Here comes some hints/steps:
$GCD | P(1)=17!$
$GCD=2^a \times 3^b \times 5^c \times 7^d \times 11^e \times 13^f \times 17^g$
Notice that $P(2)=2 \times 3 \times 5 \times \dots \times 33$ is multiple of $2$ but not $2^2$ similarly for every prime $p$, we have $P(p)$ multiple of $p$ but all the $ip+1$ factors are not so $1$ is the max prime power of each prime on GCD
for a prime $p$ for every $n$ natural either $p|n$ or
one of the numbers $n+1$, $2n+1$, ..., $(p-1)n+1$, $pn+1$ is divisible by $p$
For all primes $p<16$ we have that $p| P(n)$
for a prime $p>2$ for every $n$ natural either $p|n$ or
one of the numbers $n$, $n+1$, $2n+1$, ..., $(p-1)n+1$ is divisible by $p$
Proof: assume that there is no number divisible by $p$ then from those $1+p-1=p$ numbers there are $2$ with the same remainder mod $p$ the difference between them is multiple by $p$ and of the form either $1$, $in+1$ or $in$ for $0<i<p-1$ contradiction
$17| P(n)$
$GCD=2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17$
you know lemma 2 works for 2 too. so you could have done it in one step
ElutabeEfezino
16.10.2016 04:26
P(1) has all the prime numbers in it as well as some of their factors. P(2) neglects the fact that we can have a HCF containing a higher factor of 2 but gives us the factors of the remaining prime numbers by the continuous addition of 1 to the factors of 2 till its sixteenth factor. This done repeatedly gives us the only common factors to be the prime numbers from 1 to 17. There fore the HCF is the product of all the prime factors from 1 to 17. Which is 510510