|
1.7
Numerical Systems
1.7.1
Representation of Integers in an Arbitrary Base
The fundamental result in this subsection is given by the following theorem:
1.7. Numerical Systems
37
Theorem 1.7.1.
Let b be an integer greater than
1
. For any integer n
≥
1
there
is a unique system
(
k
,
a
0
,
a
1
, . . . ,
a
k
)
of integers such that
0
≤
a
i
≤
b
−
1
,
i
=
0
,
1
, . . . ,
k, a
k
=
0
, and
n
=
a
k
b
k
+
a
k
−
1
b
k
−
1
+ · · · +
a
1
b
+
a
0
.
(
1
)
Proof.
For the existence, we repeatedly apply the division algorithm:
n
=
q
1
b
+
r
1
,
0
≤
r
1
≤
b
−
1
,
q
1
=
q
2
b
+
r
2
,
0
≤
r
2
≤
b
−
1
,
. . .
q
k
−
1
=
q
k
b
+
r
k
,
0
≤
r
k
≤
b
−
1
,
where
q
k
is the last nonzero quotient.
Let
a
0
=
r
1
=
n
−
q
1
b
,
a
1
=
q
1
−
q
2
b
, . . . ,
a
k
−
1
=
q
k
−
1
−
q
k
b
,
a
k
=
q
k
.
Then
k
i
=
0
a
i
b
i
=
k
−
1
i
=
0
(
q
i
−
q
i
+
1
b
)
b
i
+
q
k
b
k
=
q
0
+
k
i
=
1
q
i
b
i
−
k
i
=
1
q
i
b
i
=
q
0
=
n
.
For the uniqueness, assume that
n
=
c
0
+
c
1
b
+ · · · +
c
h
b
h
is another such
representation.
If
h
=
k
, for example
h
>
k
, then
n
≥
b
h
≥
b
k
+
1
. But
n
=
a
0
+
a
1
b
+ · · · +
a
k
b
k
≤
(
b
−
1
)(
1
+
b
+ · · · +
b
k
)
=
b
k
+
1
−
1
<
b
k
+
1
,
a contradiction.
If
h
=
k
, then
a
0
+
a
1
b
+ · · · +
a
k
b
k
=
c
0
+
c
1
b
+ · · · +
c
k
b
k
,
and so
b
|
a
0
−
c
0
. On the other hand,
|
a
0
−
c
0
|
<
b
; hence
a
0
=
c
0
, Therefore
a
1
+
a
2
b
+ · · · +
a
k
b
k
−
1
=
c
1
+
c
2
b
+ · · · +
c
k
b
k
−
1
.
Repeating the procedure above, it follows that
a
1
=
c
1
,
a
2
=
c
2
, . . .
,
a
k
=
c
k
.
Relation (1) is called
the base-b representation
of
n
and is denoted by
n
=
a
k
a
k
−
1
· · ·
a
0
(
b
)
The usual
decimal representation
corresponds to
b
=
10.
38
I Fundamentals, 1. Divisibility
Examples.
(1) 4567
=
4
·
10
3
+
5
·
10
2
+
6
·
10
+
7
=
4567
(
10
)
.
(2) Let us write 1010011
(
2
)
in base 10. We have
1010011
(
2
)
=
1
·
2
6
+
0
·
2
5
+
1
·
2
4
+
0
·
2
3
+
0
·
2
2
+
1
·
2
+
1
=
64
+
16
+
2
+
1
=
83
.
(3) Let us write 1211 in base 3. As above, dividing by 3 successively, the
remainders give the digits of the base-3 representation, beginning with the last.
The first digit is the last nonzero quotient. We can arrange the computations as
follows:
1211 3
1209 403 3
2
402 134 3
1
132 44 3
2
42 14 3
2
12 4 3
2
3
1
1
Hence 1211
=
1122212
(
3
)
.
1.7.2
Divisibility Criteria in the Decimal System
We will prove some divisibility criteria for integers in decimal representation. In
this subsection, we will write
n
=
a
h
a
h
−
1
· · ·
a
0
with the understanding that we
operate in base 10.
Criterion 1.
(a) The integer n
=
a
h
a
h
−
1
· · ·
a
0
is divisible by
3
if and only if the
sum s
(
n
)
of its digits is divisible by
3
.
(b) The integer n
=
a
h
a
h
−
1
· · ·
a
0
is divisible by
9
if and only if s
(
n
)
is divisi-
ble by
9
.
Proof.
We have 10
k
≡
1
(
mod 9
)
, since 10
≡
1
(
mod 9
)
; hence
n
=
h
k
=
0
a
k
10
k
≡
h
k
=
0
a
k
≡
s
(
n
) (
mod 9
).
Both conclusions follow.
Criterion 2.
The integer n
=
a
h
a
h
−
1
· · ·
a
0
is divisible by
11
if and only if a
0
−
a
1
+ · · · +
(
−
1
)
h
a
h
is divisible by
11
.
Proof.
We have 10
k
=
(
11
−
1
)
k
≡
(
−
1
)
k
(
mod 11
)
; hence
n
=
h
k
=
0
a
k
10
k
≡
h
k
=
0
(
−
1
)
k
a
k
(
mod 11
),
and the conclusion follows.
1.7. Numerical Systems
39
Criterion 3.
The integer n
=
a
h
a
h
−
1
· · ·
a
0
is divisible by
7
,
11
, or
13
if and only
if a
h
a
h
−
1
· · ·
a
3
−
a
2
a
1
a
0
has this property.
Proof.
We have
n
=
a
2
a
1
a
0
+
(
1001
−
1
)
a
h
a
h
−
1
· · ·
a
3
=
(
7
·
11
·
13
)
a
h
a
h
−
1
· · ·
a
3
−
(
a
h
a
h
−
1
· · ·
a
3
−
a
2
a
1
a
0
),
hence the desired conclusion.
Criterion 4.
The integer n
=
a
h
a
h
−
1
· · ·
a
0
is divisible by
27
or
37
if and only if
a
h
a
h
−
1
· · ·
a
3
+
a
2
a
1
a
0
has this property.
Proof.
We have
n
=
a
2
a
1
a
0
+
(
999
+
1
)
a
h
a
h
−
1
· · ·
a
3
=
(
27
·
37
)
a
h
a
h
−
1
· · ·
a
3
+
(
a
h
a
h
−
1
· · ·
a
3
+
a
2
a
1
a
0
),
and the conclusion follows.
Examples.
(1) The integer 123456789 is divisible by 9 because the sum of its
digits 1
+
2
+ · · · +
9
=
45 has this property (Criterion 1(b)).
(2) The integer 20
. . .
04
2004
is not a perfect square because the sum of its digits is
6, a multiple of 3 but not of 9; hence the integer itself has these properties (Criteria
1(a) and 1(b)).
(3) All integers of the form
abcde f
, where
a
+
c
+
e
=
8 and
b
+
d
+
f
=
19,
are divisible by 99, because
a
+
b
+
c
+
d
+
f
=
8
+
19, a multiple of 9, and
f
−
e
+
d
−
c
+
b
−
a
=
19
−
8, a multiple of 11, and the conclusion follows
from Criteria 1(b) and 2.
(4) For any nonzero digit
a
, the integer
a
1234567 is not divisible by 37. In-
deed, applying Criterion 4, we have
a
1234
+
567
=
a
1801 and
a
1
+
801
=
8
a
2
=
800
+
10
a
+
2
=
37
·
21
+
10
a
+
25. The integer 10
a
+
25
=
5
(
2
a
+
5
)
is not
divisible by 37 because 7
≤
2
a
+
5
≤
23.
Problem 1.7.1.
Find all integers written as abcd in decimal representation and
dcba in base
7
.
Solution.
We have
abcd
(
10
)
=
dcba
(
7
)
⇔
999
a
+
93
b
=
39
c
+
342
d
⇔
333
a
+
31
b
=
13
c
+
114
d
;
hence
b
≡
c
(
mod 3
)
. Since
b
,
c
∈ {
0
,
1
,
2
,
3
,
4
,
5
,
6
}
, the possibilities are:
(i)
b
=
c
;
(ii)
b
=
c
+
3;
(iii)
b
+
3
=
c
.
40
Do'stlaringiz bilan baham: |
