17. Лекция по элементарной математике. Лекции по элементарной математике Глава Элементы теории чисел 5 Метод математической индукции 5

• Название: Лекции по элементарной математике Глава Элементы теории чисел 5 Метод математической индукции 5
• Дата: 30.03.2021
• Размер: 186.94 Kb.
• Имя файла: 17. Лекция по элементарной математике.docx
• Тип: Лекции; #189455
• страница: 9 из 25

Позиционные системы счисления.

В позиционных системах счисления значение применяемых симво- лов зависит от места, которое этот символ занимает в записи числа. Чаще всего применяют позиционные системы счисления с фиксированным основанием. В этих системах для записи натуральных чисел достаточ- но конечного множества знаков (цифр). При этом сдвиг цифры на одно место влево влечет за собой увеличение ее числового значения в g раз, где g – некоторое натуральное число, большее 1. Число g называют основа- нием системы счисления. Чаще всего применяют десятичную систему счисления, в которой g = 10. Это связано с тем, что число пальцев на ру- ках человека равно 10, а первоначально люди считали по пальцам.

Перейдем к более подробному описанию позиционной системы счис- ления с основанием g.

Определение 1. Систематической записью натурального числа N по основанию g называют представление этого числа в виде суммы:

где a_n ,..., a₁, a₀

числа, принимающие значения 0, 1, ..., g – 1, причем

a_n 0.

Позиционная система счисления с основанием g называется g-

ичной (двоичная, троичная и т. д.). На практике чаще всего при- меняется десятичная система счисления (g = 10). В быстродейст- вующих вычислительных машинах применяют двоичную и восьме- ричную системы счисления.

Для обозначения чисел 0, 1, ... , g–1 в g-ичной системе счисления используют особые знаки, называемые цифрами. Иногда для кратко- сти сами эти числа называют цифрами (что, строго говоря, неверно, так как цифры – лишь знаки для обозначения некоторых чисел). Замеча- тельным открытием древнеиндийских математиков было изобретение нуля – особого знака, который должен был показать отсутствие единиц определенного разряда.

Для g-ичной системы счисления нужно g цифр (для обозначения чи- сел от 0 до g–1). Если g<10, то применяют те же обозначения цифр, что и в десятичной системе счисления (только берут не все цифры), а если g>10, то нужны особые обозначения для чисел от 0 до g–1 (например, в двенадцатеричной системе счисления нужны еще две цифры, а в два- дцатеричной – еще десять цифр).

В двоичной системе достаточно двух цифр: 0 и 1. Именно этим, в частности, объясняется широкое использование двоичной системы счис- ления в вычислительных машинах: основные элементы вычислительных машин – особые устройства, которые могут находиться в двух положе- ниях (скажем, пропускать или не пропускать ток). Одно положение ставят в соответствии цифре 0, а другое – цифре 1.

Докажем следующую теорему о систематической записи чисел:

Теорема 1. Всякое натуральное число N может быть представле- но в виде систематической записи по любому основанию

Доказательство. Докажем сначала, что если ⁰ то число N допускает g-ичную запись в виде:

(где а_пможет равняться нулю). При этом если gⁿ то

a_n Доказательство проведем с помощью математическое индук-

ции по п. При п=0 имеем 0 N g.. В этом случае g -ичная запись

числа N состоит из одного слагаемого – самого этого числа (N = а₀).

Пусть для всех чисел, меньших gⁿ, доказано существование g-

ичной записи и пусть gⁿ N g^{n 1} . Разделим N на gⁿ c остатком N=

a_ngⁿ+ N_l, где N_lⁿ. Так как N_lⁿ, то N_l имеет g-ичную запись вида:

N₁

(где, быть может, a_n-1= 0). Но тогда

^N .

Поскольку для любого N найдется такое п, что Nⁿ⁺¹, то возмож- ность g-ичного представления доказана для всех натуральных п.

Теперь докажем, что такое представление единственно.

Если a N g, , то N может иметь лишь g-ичную запись вида N

= а₀, поскольку при n


n
a gⁿ

1, a_n

0 выполняется неравенство

Запись N = а₀ однозначно определена, поскольку все числа от 1 до g–1 обозначаются различными цифрами.

Пусть уже доказано, что g-ичная запись для чисел N, таких что

0

Если

определена однозначно и пусть gⁿ

13. 
    g^{n 1} .
    

N agⁿ

_{a g}n1

...

a g a,

n n 1 1 0

то а_п– частное от деления N на gⁿ,a ^{M a gn1 ... ag a} ос-

n 1 1 0

таток при таком делении. Значит, а_пи М однозначно определены. Но по предположению индукции g-ичная запись числа М определена однознач-

но. Значит, и цифры

a_{n 1},..., a₀

однозначно определены. Иными слова-

ми, g-ичная запись числа N однознчно определена. С помощью индук- ции по п получаем, имеют лишь одну g-ичную запись.


k

a g

k 1

a g

n 1
Выведем теперь явную формулу для записи числа N:

n
N agⁿ

^{n 1} ...

a g^k

_{k 1} a₀ . (2)

Для это разделим обе части равенства (2) на

g^k , 0

k n.

Т.к. ^a

то имеем: ^{ak 1} ... ^a0 1,

k
и потому

g g^k

Точно так же устанавливаем, что

E

(3^/ )

Из равенств (3) и (3') вытекает, что

a_k

Вместо громоздкой записи

N

обычно пишут N .

Черта сверху пишется для того, чтобы отличить эту запись от произ-

ведения чисел

a_n ...a₁a₀ . Индекс g (справа внизу) указывает, по какому

основанию записано число. При записи конкретного числа черта опус- кается. В десятичной системе счисления индекс 10 не ставится.

Пример 1. Найти десятичную запись числа

2346₇ .

2346₇

2 7³

3 7²

^{4 7 6 867} .

Проверим, переведем 867 в 7-ичную систему счисления.

867	7
7	123	7
16	7	17	7
14	53	14	2	7
27	49	3	0	0
21	4		2
6

Ответ: ⁸⁶⁷

Пример 2. Число ления.

23012₄

перевести в пятеричную систему счис-

1 способ.

23012₄

710	5
5	142	5
21	10	28	5
20	42	25	5	5
10	40	3	5	1	5
10	2		0	0	0
0				1

Ответ: 23012₄