Number Theory: Structures, Examples, and Problems

I Fundamentals, 1. Divisibility
On the other hand, none of the numbers listed in (1) is divisible by
b
. Indeed,
if so, then there is
k
∈ {
1
,
2
, . . . ,
n
−
1
}
such that
k
·
a
=
p
·
b
for some integer
p
.
Let
d
be the greatest common divisor of
k
and
p
. Then
k
=
k
1
d
,
p
=
p
1
d
,
for some integers
p
1
,
k
1
with gcd
(
p
1
,
k
1
)
=
1. Hence
k
1
a
=
p
1
b
, and since
gcd
(
a
,
b
)
=
1, we have
k
1
=
b
,
p
1
=
a
. This is false, because
k
1
<
b
.
It follows that one of the numbers from (1) has the remainder 1 when divided
by
b
, so there is
u
∈ {
1
,
2
, . . . ,
b
−
1
}
such that
au
=
b
v
+
1 and the lemma is
proved. In fact, there are infinitely many positive integers
u
and
v
satisfying this
property, that is,
u
=
u
0
+
kb
,
v
=
v
0
+
ka
, where
u
0
and
v
0
satisfy
au
0
−
b
v
0
=
1.
We now prove that the system
ax
−
yz
−
c
=
0
,
bx
−
yt
+
d
=
0
,
with
a
,
b
,
c
,
d
nonnegative integers and gcd
(
a
,
b
)
=
1, has infinitely many solu-
tions in nonnegative integers.
Because gcd
(
a
,
b
)
=
1, using the lemma, we see that there are infinitely many
positive integers
u
and
v
such that
au
−
b
v
=
1. Hence
x
=
cu
+
d
v,
y
=
ad
+
bc
,
z
=
v,
t
=
u
,
are solutions to the system.
Problem 1.3.3.
Find all the pairs of integers
(
m
,
n
)
such that the numbers A
=
n
2
+
2
mn
+
3
m
2
+
2
, B
=
2
n
2
+
3
mn
+
m
2
+
2
, C
=
3
n
2
+
mn
+
2
m
2
+
1
have
a common divisor greater than
1
.
Solution.
A common divisor of
A
,
B
, and
C
is also a divisor for
D
=
2
A
−
B
,
E
=
3
A
−
C
,
F
=
5
E
−
7
D
,
G
=
5
D
−
E
,
H
=
18
A
−
2
F
−
3
E
,
I
=
nG
−
m F
,
and 126
=
18
n I
−
5
H
+
11
F
=
2
·
3
2
·
7. Since
A
+
B
+
C
=
6
(
m
2
+
mn
+
n
2
)
+
5,
it follows that 2 and 3 do not divide
A
,
B
, and
C
. Therefore
d
=
7. We get that
(
m
,
n
)
is equal to
(
7
a
+
2
,
7
b
+
3
)
or
(
7
c
+
5
,
7
d
+
4
)
.
Problem 1.3.4.
Let n be an even positive integer and let a
,
b be positive coprime
integers. Find a and b if a
+
b divides a
n
+
b
n
.
(2002 Romanian Mathematical Olympiad)
Solution.
Since
n
is even, we have
a
n
−
b
n
=
(
a
2
−
b
2
)(
a
n
−
2
+
a
n
−
4
b
2
+ · · · +
b
n
−
2
).
Since
a
+
b
is a divisor of
a
2
−
b
2
, it follows that
a
+
b
is a divisor of
a
n
−
b
n
. In
turn,
a
+
b
divides 2
a
n
=
(
a
n
+
b
n
)
+
(
a
n
−
b
n
)
, and 2
b
n
=
(
a
n
+
b
n
)
−
(
a
n
−
b
n
)
.
But
a
and
b
are coprime numbers, and so gcd
(
2
a
n
,
2
b
n
)
=
2. Therefore
a
+
b
is
a divisor of 2; hence
a
=
b
=
1.

---

1.3. The Greatest Common Divisor and Least Common Multiple
23
Problem 1.3.5.
M is the set of all values of the greatest common divisor d of the
numbers A
=
2
n
+
3
m
+
13
, B
=
3
n
+
5
m
+
1
, C
=
6
n
+
8
m
−
1
, where m and
n are positive integers. Prove that M is the set of all divisors of an integer k.
Solution.
If
d
is a common divisor of the numbers
A
,
B
, and
C
, then
d
divides
E
=
3
A
−
C
=
m
+
40,
F
=
2
B
−
C
=
2
m
+
3, and
G
=
2
E
−
F
=
77.
Hence
d
must be a divisor of 77. To complete the problem we need only show
that every divisor of 77 occurs as
d
for some
m
and
n
. Taking
m
=
n
=
1
gives
(
A
,
B
,
C
)
=
(
18
,
9
,
13
)
and hence
d
=
1. If
d
=
7, then 7
|
2
m
+
3.
The smallest solution is
m
=
2. Taking
m
=
2 and
n
=
1 gives
(
A
,
B
,
C
)
=
(
21
,
14
,
21
)
and
d
=
7, as desired. If
d
=
11, then 11
|
2
m
+
3, which has
smallest solution
m
=
4. Taking
m
=
n
=
4 gives
(
A
,
B
,
C
)
=
(
33
,
33
,
55
)
and
d
=
11, as desired. If
d
=
77, then 77
|
2
m
+
3. Taking
m
=
37 and
n
=
15 gives
(
A
,
B
,
C
)
=
(
154
,
231
,
385
)
and
d
=
77.
Problem 1.3.6.
Let a, b, and c be integers. Prove that
gcd
(
a
,
b
)
gcd
(
b
,
c
)
gcd
(
c
,
a
)
gcd
(
a
,
b
,
c
)
2
and
lcm
(
a
,
b
)
lcm
(
b
,
c
)
lcm
(
c
,
a
)
lcm
(
a
,
b
,
c
)
2
are equal integers.
Solution.
Let
a
=
p
α
1
1
· · ·
p
α
n
n
,
b
=
p
β
1
1
· · ·
p
β
n
n
, and
c
=
p
γ
1
1
· · ·
p
γ
n
n
, where
p
1
, . . . ,
p
n
are distinct primes, and
α
1
, . . . , α
n
, β
1
, . . . , β
n
, γ
1
, . . . , γ
n
are non-
negative integers. Then
gcd
(
a
,
b
)
gcd
(
b
,
c
)
gcd
(
c
,
a
)
gcd
(
a
,
b
,
c
)
2
=
n
i
=
1
p
min
{
α
i
,β
i
}
i
n
i
=
1
p
min
{
β
i
,γ
i
}
i
n
i
=
1
p
min
{
γ
i
,α
i
}
i
n
i
=
1
p
2 min
{
α
i
,β
i
,γ
i
}
i
=
n
i
=
1
p
min
{
α
i
,β
i
}+
min
{
β
i
,γ
i
}+
min
{
γ
i
,α
i
}−
2 min
{
α
i
,β
i
,γ
i
}
i
and
lcm
(
a
,
b
)
lcm
(
b
,
c
)
lcm
(
c
,
a
)
lcm
(
a
,
b
,
c
)
2
=
n
i
=
1
p
max
{
α
i
,β
i
}
i
n
i
=
1
p
max
{
β
i
,γ
i
}
i
n
i
=
1
p
max
{
γ
i
,α
i
}
i
n
i
=
1
p
2 max
{
α
i
,β
i
,γ
i
}
i
=
n
i
=
1
p
max
{
α
i
,β
i
}+
max
{
β
i
,γ
i
}+
max
{
γ
i
,α
i
}−
2 max
{
α
i
,β
i
,γ
i
}
i
.

---

24