2008 iTest Problems/Problem 94
Problem
Find the largest prime number less than that is a divisor of some integer in the infinite
sequence
Solution
Solution 1
The largest prime number less than is
; we claim that this is the answer. Indeed, we claim that the
th term divides
, where
is prime (and hence relatively prime to
).
To do so, we claim that
holds, and since is prime the result follows. Indeed,
, where
denotes the fractional part of a number. So
becomes
By Fermat's Little Theorem, we have , so
. Also,
is equivalent to the remainder when
is divided by
, and by Fermat's Little Theorem again, we have
. Hence, equation
reduces to
as desired.
Solution 2 (Official Solution)
Fermat's Little Theorem tells us that for a prime that is not a divisor of
,
, so
. When
, then
Now that we have an expression to work with that doesn't involve the floor function, we begin to manipulate it in order to make it useful:
The most general piece we have to work with is the summation
. We look for some way to determine which primes
can be factors of this expression. So long as
, then by Fermat's Little Theorem,
divides
and so
Now we note that
divides evenly into
when
is a divisor of
. So, if there exists such a prime
, then
is a divisor of some term of the given sequence. Dirichlet's Theorem guarantees that within the arithmetic sequence
there are infinitely many primes. ONe of them,
implies that
. For sufficiently large
, this completes our proof that each prime
that is relatively prime to
and
must be a divisor of some term in the given sequence. The largest prime less than
is
, which is our answer.