Таблицы Брадиса

Говорят также, что делит а.

Говорят также, что делит а.

Элементы математики в задачах - Г. А. Мерзон

наиболее популярных криптографических систем RSA основана как раз на том, что даже зная, что (достаточно большое) число m имеет ровно два простых множителя, найти их — очень сложная задача.

Соглашение. Все числа в этом листке предполагаются целыми.

Определение 1. Целое число а делится на ненулевое целое число

b, если существует такое целое число к, что a = kb. В этом случае b называется делителем а. Говорят также, что b делит а. Обозначения: а. b или b | а.

Задача 1. Докажите, что для любого а:

а) если а = 0, то а. а; б) а. 1; в) если а = 0, то 0. а.

Решение. а) а = 1 ■ а; б) а = а ■ 1; в) 0 = а ■ 0.

Задача 2. Докажите, что для любых а, b, c, х, у:

а) если а. b и b. c, то а. с;

б) если а. b и а = 0, то |а| ^ |b|;

в) если с = 0, то а. b ^ ас. bc;

г) если а. b и с. b, то (а ± с). b;

д) если а. b и с. b, то ах + су. b;

е) если а. b и b. а, то а = b или а = —b;

ж) если а. b, то ас. b;

з) если а. b и с/b, то (а + с) /b;

и) если ab = с<і и а . с, то d. b.

Решение. а) Запишем делимость в виде равенств: а. b ^ 3k є Z : а = = kb, аналогично b. с ^ 3l є Z : b = 1с. Получаем а = кіс ^ а. с;

б)  а. b и а = 0 ^ Зк є Z : а = bk ^ |а| = |bk| = |b|■|k| ^ |а| ^ |b|, так как |k| ^ 1;

в) а ; b ^ 3k є Z : а = bk. Обе части равенства можно домножить на ненулевое число с. Получаем ас = bck. Что и требовалось доказать. Обратное утверждение докажите самостоятельно.

г)  а . b и с . b ^ 3k, І є Z : (а = bk, с = bl) ^ а ± c = bk ± bl = = b(k ± і) і b.

д) а . b и с. b ^ 3k, І є Z : (а = bk, c = bl) ^ ах + су = bkx + bly = = b(kx + ly). b;

е) а. b и b. а ^ 3k, l є Z : (а = bk, b = а0 ^ а = bk = аіk ^ lk = 1 ^ ^ (l = 1, k = 1) или (l = —1, k = —1);

ж)  а. b ^ 3k є Z : а = bk ^ ас = bkc ^ ас. b;

з)  Докажем от противного[17]. Пусть а + с . b, а . b, с / b, тогда 3k, l є Z : (а + с = bk, а = bl) ^ (а + с) — а = с = bk — bl = b(k — l) ^ c. b. Противоречие.

Г. А. Мерзон: Элементы математики в задачах. Часть 1.