Number Theory: Structures, Examples, and Problems


I Fundamentals, 9. Some Special Problems in Number Theory



Download 1,87 Mb.
Pdf ko'rish
bet68/125
Sana08.02.2022
Hajmi1,87 Mb.
#434761
1   ...   64   65   66   67   68   69   70   71   ...   125
Bog'liq
Titu Andreescu, Dorin Andrica Number Theory Str

I Fundamentals, 9. Some Special Problems in Number Theory
Solution.
Assume that we have a prime
p
such that
p
|
2
n
+
1 and
p
≡ −
1
(
mod 8
)
. If
n
is even, then
p

3
(
mod 4
)
and

1
p
=
1, a contradiction. If
n
is odd, 2
n
≡ −
1
(
mod
p
)
, and so

2

(
2
n
+
1
2
)
2
(
mod
p
)
; hence

2
p
=
1. We
get
(

1
)
p
2

1
8
(

1
)
p

1
2
=
1, again a contradiction.
Problem 9.1.5.
Prove that
2
3
n
+
1
has at least n prime divisors of the form
8
k
+
3
.
Solution.
Using the result of the previous problem, we deduce that 2
n
+
1 does
not have prime divisors of the form 8
k
+
7. We will prove that if
n
is odd, then it
has no prime divisors of the form 8
k
+
5 either. Indeed, let
p
be a prime divisor of
2
n
+
1. Again we have 2
n
≡ −
1
(
mod
p
)
and so

2

(
2
n
+
1
2
)
2
(
mod
p
)
. Using
the same argument as the one in the previous problem, we deduce that
p
2

1
8
+
p

1
2
is even, which cannot happen if
p
is of the form 8
k
+
5.
Now, let us solve the additional problem. We will assume
n
>
2 (otherwise,
the verification is trivial). The essential observation is the identity
2
3
n
+
1
=
(
2
+
1
)(
2
2

2
+
1
)(
2
2
·
3

2
3
+
1
)
· · ·
(
2
2
·
3
n

1

2
3
n

1
+
1
).
Now we will prove that for all 1

i
<
j

n

1,
gcd
(
2
2
·
3
i

2
3
i
+
1
,
2
2
·
3
j

2
3
j
+
1
)
=
3
.
Indeed,
2
3
j
=
(
2
3
i
+
1
)
3
j

i

1

(

1
)
3
j

i

1
≡ −
1
(
mod 2
3
i
+
1
+
1
),
implying
2
2
·
3
j

2
3
j
+
1

3
(
mod 2
3
i
+
1
+
1
).
Therefore the greatest common divisor is at most 3. Since
2
2
·
3
i

2
3
i
+
1

1

(

1
)
+
1
=
3
(
mod 3
),
both quantities are divisible by 3 and therefore the greatest common divisor is 3,
as claimed.
It remains to show that each of the numbers 2
2
·
3
i

2
3
i
+
1, with 1

i

n

1
has at least one prime divisor of the form 8
k
+
3 different from 3. It would follow in
this case that 2
3
n
+
1 has at least
n

1 distinct prime divisors of the form 8
k
+
3
(from the previous remarks), and since it is also divisible by 3, the conclusion
would follow. Fix
i
∈ {
1
,
2
, . . . ,
n

1
}
and observe that any prime factor of
2
2
·
3
i

2
3
i
+
1, is also a prime factor of 2
3
n
+
1, and thus, from the first remark, it
must be of the form 8
k
+
1 or 8
k
+
3. Because
v
3
(
2
2
·
3
i

2
3
i
+
1
)
=
1, it follows
that if all prime divisors of 2
2
·
3
i

2
3
i
+
1 except for 3 are of the form 8
k
+
1,


9.1. Quadratic Residues; the Legendre Symbol
175
then 2
2
·
3
i

2
3
i
+
1

3
(
mod 8
)
, which is clearly impossible. Thus at least one
prime divisor of 2
2
·
3
i

2
3
i
+
1 is different from 3 and is of the form 8
k
+
3, and
so the claim is proved. The conclusion follows.
Problem 9.1.6.
Find a number n between
100
and
1997
such that n
|
2
n
+
2
.
(1997 Asian-Pacific Mathematical Olympiad)
Solution.
The first step would be choosing
n
=
2
p
, for some prime number
p
.
Unfortunately, this cannot work by Fermat’s little theorem. So let us try setting
n
=
2
pq
, with
p
,
q
different prime numbers. We need
pq
|
2
2
pq

1
+
1, and so we
must have

2
p
=

2
q
=
1. Also, using Fermat’s little theorem,
p
|
2
2
q

1
+
1
and
q
|
2
2
p

1
+
1. A small verification shows that
q
=
3
,
5
,
7 are not good
choices, so let us try
q
=
11. In this case we obtain
p
=
43, and so it suffices
to show that
pq
|
2
2
pq

1
+
1 for
q
=
11 and
p
=
43. This is immediate, since
the hard work has already been completed: we have shown that it suffices to have
p
|
2
2
q

1
,
q
|
2
2
p

1
+
1, and

2
p
=

2
q
=
1 in order to have
pq
|
2
2
pq

1
+
1.
But as one can easily check, all these conditions are satisfied, and the number
2
·
11
·
43
=
946 is a valid answer.
Additional Problems
Problem 9.1.7.
Let
f
,
g
:
Z
+

Z
+
functions with the following properties:
(i)
g
is surjective;
(ii) 2
f
2
(
n
)
=
n
2
+
g
2
(
n
)
for all positive integers
n
.
If, moreover,
|
f
(
n
)

n
| ≤
2004

n
for all
n
, prove that
f
has infinitely many
fixed points.
(2005 Moldavian International Mathematical Olympiad Team Selection Test)
Problem 9.1.8.
Suppose that the positive integer
a
is not a perfect square. Then
a
p
= −
1 for infinitely many primes
p
.
Problem 9.1.9.
Suppose that
a
1
,
a
2
, . . . ,
a
2004
are nonnegative integers such that
a
n
1
+
a
n
2
+ · · · +
a
n
2004
is a perfect square for all positive integers
n
. What is the
minimal number of such integers that must equal 0?
(2004 Mathlinks Contest)
Problem 9.1.10.
Find all positive integers
n
such that 2
n

1
|
3
n

1.
(American Mathematical Monthly)
Problem 9.1.11.
Find the smallest prime factor of 12
2
15
+
1.


176
I Fundamentals, 9. Some Special Problems in Number Theory
9.2
Special Numbers
9.2.1
Fermat Numbers
Trying to find all primes of the form 2
m
+
1, Fermat noticed that
m
must be a
power of 2. Indeed, if
m
equaled
k
·
h
with
k
an odd integer greater than 1, then
2
m
+
1
=
(
2
h
)
k
+
1
=
(
2
h
+
1
)(
2
h
(
k

1
)

2
h
(
k

2
)
+ · · · −
2
h
+
1
),
and so 2
m
+
1 would not be a prime.
The integers
f
n
=
2
2
n
+
1,
n

0, are called
Fermat numbers
. We have
f
0
=
3
,
f
1
=
5
,
f
2
=
17
,
f
3
=
257
,
f
4
=
65
,
573
.
After checking that these five numbers are primes, Fermat conjectured that
f
n
is a prime for all
n
. But Euler proved that 641
|
f
5
. His argument was the
following:
f
5
=
2
32
+
1
=
2
28
(
5
4
+
2
4
)

(
5
·
2
7
)
4
+
1
=
2
28
·
641

(
640
4

1
)
=
641
2
28

639
(
640
2
+
1
)
.
It is still an open problem whether there are infinitely many Fermat primes.
Also, the question whether there are any Fermat primes after
f
4
is still open. The
answer to this question is important, because Gauss proved that a regular polygon
Q
1
Q
2
. . .
Q
n
can be constructed using only a straightedge and compass if and
only if
n
=
2
h
p
1
· · ·
p
k
, where
k

0 and
p
1
, . . . ,
p
k
are distinct Fermat primes.
Gauss was the first to construct such a polygon for
n
=
17.
Problem 9.2.1.
Prove that for f
n
, the nth Fermat number,
(i) f
n
=
f
0
· · ·
f
n

1
+
2
,
n

1
;
(ii)
gcd
(
f
k
,
f
h
)
=
1
if k
=
h;
(iii) f
n
ends in
7
for all n

2
.
Solution.
(i) We have
f
k
=
2
2
k
+
1
=
2
2
k

1
2
+
1
=
(
f
k

1

1
)
2
+
1
=
f
2
k

1

2
f
k

1
+
2
;
hence
f
k

2
=
f
k

1
(
f
k

1

2
),
k

1
.
(
1
)
Multiplying relations (1) for
k
=
1
, . . . ,
n
yields
f
n

2
=
f
0
· · ·
f
n

1
(
f
0

2
),
and the conclusion follows.



Download 1,87 Mb.

Do'stlaringiz bilan baham:
1   ...   64   65   66   67   68   69   70   71   ...   125




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish