A number theory problem from Mathematical Reflections
by XmL, Jul 4, 2014, 4:52 AM
Problem(MR5 2013 O.285):Let
be the sequence of integers defined as
and
for
. Prove that
divides 
A super long solution






A super long solution
Lemma 1:
are positive integer,
.
Proof: The if part is
, for the only if part: let
where
are integers and
.
Since
, hence
. Since
, hence
.
Original problem: We will first show that
by induction:
Base case:
Inductive step: assume that the statement is true for all
up to
, we will show that it's true for
. Indeed:
and by Lemma 1
which is true by assumption.
Next we will show with induction again that if an odd prime
satisfies
, then
:
We go straight to the step: Assuming that
, we will show 
. By the result above
for all
. By a well known lemma:
(note that
since
), therefore
.
Finally we are going to show
where
is an odd prime
and
together using induction.
Base case:
because
.
.
Inductive Step: Assuming that the statement is true up to
and all odd primes(not 3) less than
, we proceed in two steps:
Step 1: If
is a prime, then we have to show
. Since by our assumption that
and it's well known that
, hence
and we are done.
Step 2: Whether
is a prime or not, we will show
by first proving all odd prime powers but
in
, denoted by
, divide
, in other words
, which is equivalent to
. Since
is obvious, we just have to worry about 
By our assumption:
, we will prove
, hence giving
. We have to prove
which is true shown in*.
Now we will deal with primes
individually:
is straight forward:
.
For
, as we've seen, it doesn't divide
but
, hence we have
. We want to prove
which is true for
and we are done.
*To show that
is true, for convinience let
or
which is true for our scenario.


Proof: The if part is









Original problem: We will first show that

Base case:

Inductive step: assume that the statement is true for all





Next we will show with induction again that if an odd prime



We go straight to the step: Assuming that









Finally we are going to show




Base case:



Inductive Step: Assuming that the statement is true up to


Step 1: If





Step 2: Whether










By our assumption:




Now we will deal with primes



For







*To show that



This post has been edited 4 times. Last edited by XmL, Aug 12, 2014, 11:15 PM