|
7.1. Congruences Modulo a Prime: Fermat’s Little Theorem
303
we obtain the decomposition
2
3
k
m
+
1
=
(
2
m
+
1
)(
2
2
m
−
2
m
+
1
)(
2
2
·
3
m
−
2
3
m
+
1
)
· · ·
(
2
2
·
3
k
−
1
m
−
2
3
k
−
1
m
+
1
). (
1
)
Let us remark that 2
3
≡ −
1
(
mod 9
)
; hence 2
3
k
≡ −
1
(
mod 9
)
for all
k
≥
1.
Since 2
2
s
−
2
s
+
1
≡
3
(
mod 9
)
for
s
of the form 3
j
, we obtain in (1) that
3
k
|
(
2
2
m
−
2
m
+
1
)(
2
2
·
3
m
−
2
3
m
+
1
)
· · ·
(
2
2
·
3
k
−
1
m
−
2
3
k
−
1
m
+
1
)
but 3
k
+
1
does not divides the product. Therefore, 3
k
|
2
m
+
1. Since 3 does not
divide
m
and
2
m
+
1
=
(
3
−
1
)
m
+
1
=
3
m
−
m
1
3
m
−
1
+· · ·−
m
m
−
1
3
≡ −
3
m
(
mod 9
),
we obtain
k
=
1.
Now we have
n
=
3
m
and 9
m
2
|
2
3
m
+
1. We repeat, in some way, the starting
argument. Take
q
the least prime divisor of
m
, 2
6
m
≡
1
(
mod
q
)
, 2
q
−
1
≡
1
(
mod
q
)
, and
δ
=
gcd
(
6
m
,
q
−
1
)
. By the definition of
q
we can have
δ
=
1
,
2
,
3
or 6 and we also have 2
δ
≡
1
(
mod
q
)
. Thus
q
can be chosen among prime
divisors of the numbers 3, 7, 63. Since
q
>
3, we can have only
q
=
7. Returning
to
m
2
|
2
3
m
+
1, we obtain 49
|
2
3
m
+
1. But we have 2
3
m
+
1
≡
2
(
mod 7
)
, and
we get a contradiction.
Thus,
m
=
1 and
n
=
3.
Problem 7.1.16.
Prove that n
|
2
n
−
1
+
1
fails for all n
>
1
.
(Sierpi´nski)
Solution.
Although very short, the proof is tricky. Let
n
=
s
i
=
1
p
k
i
i
, where
p
1
<
· · ·
<
p
s
are prime numbers. The idea is to look at
v
2
(
p
i
−
1
)
. Choose the
p
i
that minimizes this quantity and write
p
i
=
1
+
2
r
i
m
i
with
m
i
odd. Then of course
we have
n
≡
1
(
mod 2
r
i
)
. Hence we can write
n
−
1
=
2
m
t
. We have 2
2
ti
t
≡ −
1
(
mod
p
i
)
; thus we surely have
−
1
≡
2
2
ri
tm
i
≡
2
(
p
i
−
1
)
t
≡
1
(
mod
p
i
)
(the last
congruence being derived from Fermat’s theorem). Thus
p
i
=
2, which is clearly
impossible.
Problem 7.1.17.
Prove that for any natural number n, n
!
is a divisor of
n
−
1
k
=
0
(
2
n
−
2
k
).
Solution.
Let us take a prime number
p
. Of course, for the argument to be nontriv-
ial, we take
p
≤
n
(otherwise, it doesn’t divide
n
!
). First, let us see what happens
with
p
=
2. We have
e
2
(
n
)
=
n
−
S
2
(
n
)
≤
n
−
1
304
II Solutions, 7. More on Divisibility
and also
v
2
n
−
1
k
=
0
(
2
n
−
2
k
)
=
n
−
1
k
=
0
v
2
(
2
n
−
2
k
)
≥
n
−
1
(since 2
n
−
2
k
is even for
k
≥
1), so we are done with this case. Now let us
assume that
p
>
2. We have
p
|
2
p
−
1
−
1 from Fermat’s theorem, so we also
have
p
|
2
k
(
p
−
1
)
−
1 for all
k
≥
1. Now,
n
−
1
k
=
0
(
2
n
−
2
k
)
=
2
n
(
n
−
1
)
2
n
k
=
1
(
2
k
−
1
)
and so from the above remarks we infer that
v
p
n
−
1
k
=
0
(
2
n
−
2
k
)
=
n
k
=
1
v
p
(
2
k
−
1
),
≥
1
≤
k
(
p
−
1
)
≤
n
v
p
(
2
k
(
p
−
1
)
−
1
)
≥
card
{
k
|
1
≤
k
(
p
−
1
)
≤
n
}
.
Since
card
{
k
|
1
≤
k
(
p
−
1
)
≤
n
} =
%
n
p
−
1
&
,
we have found that
v
p
n
−
1
k
=
0
(
2
n
−
2
k
)
≥
%
n
p
−
1
&
.
But we know that
e
p
(
n
)
=
n
−
s
p
(
n
)
p
−
1
≤
n
−
1
p
−
1
<
n
p
−
1
,
and since
e
p
(
n
)
is an integer, we must have
e
p
(
n
)
≤
%
n
p
−
1
&
.
From these two inequalities, we conclude that
v
p
A
n
−
1
k
=
0
(
2
n
−
2
k
)
B
≥
e
p
(
n
),
and now the problem is solved.
7.2. Euler’s Theorem
305
7.2
Euler’s Theorem
Problem 7.2.5.
Prove that for every positive integer n, there exists a polynomial
with integer coefficients whose values at
1
,
2
, . . . ,
n are different powers of
2
.
(1999 Hungarian Mathematical Olympiad)
Solution.
It suffices to prove the claim when
n
≥
4, because the same polynomial
that works for
n
≥
4 works for
n
≤
3. For each
i
=
1
,
2
, . . . ,
n
, consider the
product
s
i
=
n
j
=
1
,
j
=
i
(
i
−
j
)
. Because
n
≥
4, one of the terms
i
−
j
equals 2,
and
s
i
is even. Thus, we can write
s
i
=
2
q
i
m
i
for positive integers
q
i
,
m
i
with
m
i
odd. Let
L
=
max
(
q
i
)
. For each
i
there are infinitely many powers of 2 that are
congruent to 1 mod
m
i
. (Specifically, by Euler’s theorem, 2
φ(
m
i
)
j
≡
1
(
mod
m
i
)
for all
j
≥
0.) Thus there are integers
c
i
such that
c
i
m
i
+
1 is a power of 2. Choose
such a
c
i
so that
c
i
m
i
+
1 are distinct powers of 2, and define
P
(
x
)
=
2
L
+
n
i
=
1
c
i
2
L
−
q
i
j
=
i
(
x
−
j
).
For each
k
, 1
≤
k
≤
n
, the term
j
=
i
(
x
−
j
)
vanishes at
x
=
k
unless
k
=
i
.
Therefore
P
(
k
)
=
2
L
+
c
k
2
L
−
q
k
j
=
k
(
k
−
j
)
=
2
L
(
c
k
m
k
+
1
),
a power of 2. Moreover, since we choose the
c
i
m
i
+
1 to be distinct, they are
different powers of 2, as needed.
Problem 7.2.6.
Let a
>
1
be an odd positive integer. Find the least positive integer
n such that
2
2000
is a divisor of a
n
−
1
.
(2000 Romanian International Mathematical Olympiad Team Selection Test)
Solution.
Since
a
is odd,
(
a
,
2
k
)
=
1, for any
k
≥
0. Hence, by Euler’s the-
orem,
a
ϕ(
2
k
)
≡
1
(
mod 2
k
)
. Since
ϕ(
2
k
)
=
2
k
−
1
and we are looking for the
least exponent
n
such that
a
n
≡
1
(
mod 2
2000
)
, it follows that
n
is a divisor of
2
1999
=
ϕ(
2
2000
)
.
If
a
≡
1
(
mod 2
2000
)
, it follows that
n
=
1. We shall omit this case.
Consider the decomposition
a
2
m
−
1
=
(
a
−
1
)(
a
+
1
)(
a
2
+
1
)(
a
2
2
+
1
)
· · ·
(
a
2
m
−
1
+
1
).
Assume
a
≡
1
(
mod 2
s
)
and
a
≡
1
(
mod 2
s
+
1
)
, where 2
≤
s
≤
1999.
That is,
a
=
2
s
b
+
1, where
b
is an odd number. Equivalently,
a
has the binary
representation
a
=
1
. . .
1 00
. . .
1
s
digits
.
306
Do'stlaringiz bilan baham: |
