Задание с экзамена по защите информации
Нужно доказать, что
Статья ориентирована на студентов, заинтересованных граждан и просто зевак. У нас защита информации была на пятом курсе в институте. На лекциях по защите информации было много историй о нелегкой судьбе русских программистов в шальные девяностые: как им платили за работу пельменями, которые делались на цокольном этаже предприятия, где они работали, как делается самогон и т.п. А оставшееся время лекции посвящалось собственно аспектам защиты информации. На лекциях давалось очень много теории по темам, хоть как-то связанным с алгоритмами шифрования. На экзамене в каждом билете было пара вопросов по теории и одна задачка.
За день до нашего экзамена ребята с параллельной группы скинули одну задачку (описана в начале статьи), решить которую не смогли. Сидела я на работе, думала, как ее решить, около часа. Какие идеи и первые мысли по решению были у меня в голове на тот момент, я не скажу, уже несколько лет прошло. Кстати мне на экзамене попалась задачка такого же типа. Ниже покажу доказательство двух типовых задачек. Если вы знаете, как доказать по-другому, отпишитесь в комментариях.
Итак, приступим. Доказательство построено с использованием теоремы Эйлера.
Еще раз повторю задание. Нужно доказать, что 
делится на 12 для всех простых x > 3.
x и 12 — взаимно простые, тогда по т.Эйлера, 
делится на 12, т.е. остаток от деления равен 0 (в теореме единица перенесена в правую часть равенства, сделаем так же): 
Для числа 12 существует четыре меньших него и взаимно простых с ним чисел (1, 5, 7, 11), поэтому функция Эйлера принимает значение четыре:
Перенесем единицу из правой части равенства влево и воспользуемся формулой из школы, разложим на множители разность квадратов:
Сокращаем на 
:
Что и требовалось доказать.
А теперь вот вам еще одна типовая задачка, которая попалась мне на экзамене. Когда решение было показано преподу, он почему-то был удивлен, поскольку, как он потом сказал, было бы достаточно просто посчитать в лоб, возвести в степень и показать, что одно число делится на другое. А решение, которое я ему показала, он видит впервые. Вот всегда думаешь, что для доказательства нужно применить теоремы, следствия, аксиомы, а оказывается «можно было просто в лоб посчитать».
Доказать, что число 
делится на 105.
Если число делится нацело, то остаток 0. Числа 73 и 105 — взаимно простые => по т. Эйлера:
Вычисляем функцию Эйлера. Поскольку перебирать все числа меньше 105 и искать взаимно простые со 105 долго, разложим 105 на множители и найдем функцию Эйлера для каждого из них, а после просто перемножим: 
Переносим единицу влево и раскладываем на множители: 
Сокращаем на 
:
Разложим на множители и сократим еще раз:
Остаток от деления на 105 — ноль, деление нацело. Ч.т.д.
Возможно, кому-то пригодится это решение, но, надеюсь, что у вас на ЗИ будет что-то поинтереснее.
Комментарии (9)
17 декабря 2016 в 17:02
0↑
↓
Поправьте меня, если я что-то пропустил, но не нужно ли перед тем как сокращать x^2 + 1 показать, что он взаимно прост с 12?17 декабря 2016 в 17:03
0↑
↓
Нужно, спасибо, что поправили17 декабря 2016 в 17:08
+7↑
↓
Незачто. Кажется что для этой задачи есть гораздо более простое решение без теоремы Эйлера, а пользуясь только школьными знаниями: рассмотрим 3 числа p-1, p и p+1. Одно из них точно делится на 3, и по-условию это не p, кроме того p-1 и p+1 — оба четные. Собираем все вместе (p-1)(p+1) делится на 3 и на 2^2, т. е. делится на 12.17 декабря 2016 в 17:26
0↑
↓
Совершенно верно, эта задачка из старых олимпиадных для младших классов.
PapaBubaDiop
17 декабря 2016 в 18:02
0↑
↓
73^12 — 1 делится на 105?
также решается без вычислений
105 = 3×5 * 7,
1) деление на 3 доказывается вашим способом, поскольку 73^6 — не делится на 2 и 3.
2) деление на 5 простое возведение в степень разряда единиц 3^2 = 9, 9^2 = 81, 1 в любой степени 1, вычитаем 1 = искомое число кратно 10, то есть делится на 5
3) деление на 7 — 73^3+1 делится на 7 поскольку куб суммы (70+3)^3 = все члены разложения делятся на 7 кроме 3^3=27, но ведь +1)) = 28 тоже чики.
17 декабря 2016 в 17:29
+1↑
↓
Вы просто написали, что x^2 + 1 взаимно просто с 12, но не объяснили почему — это как-то странно. Мне вот например, не очевидно почему это так.
17 декабря 2016 в 17:40
+1↑
↓
Я скажу больше. x*x — 1 делится на 24 для всех простых x > 317 декабря 2016 в 18:31
0↑
↓
Мне кажется, доказать можно проще:
- Раскладываем на
- Т.к.
— простое и нечетное, то
и
— четные =>
⋮ 4
- Среди n подряд идущих натуральных чисел существует единственное ⋮ n (одно из свойств делимости натуральных чисел). Возьмем 3 подряд идущих:
.
⋮ 3
⋮ 3;
17 декабря 2016 в 18:43 (комментарий был изменён)
0↑
↓
Из двух соседних четных одно обязательно делится на 4. То есть (x-1)(x + 1) ⋮ 8
- Раскладываем на
