1.22 Докажите или опровергните такое утверждение: если у a есть обратное по модулю b, то и у b есть обратное по модулю a.

Решение. В тексте главы есть утверждение:

У числа a есть обратное по модулю N тогда и
только тогда, когда a и N взаимно просты.

Из которого следует решение. Но доказательства нету, поэтому можно свести задачку к доказательству утверждения.

xa = 1 mod b <=> a, b взаимно просты

В одну сторону:
пусть r -- наибольший общий делить a, b. Тогда представим a = qr, b = wr:
xqr = 1 mod wr => xqr = dwr + 1, где x,q,r,d,w -- натуральные(?)
xq = dw + 1/r => r = 1 => значит наибольший общий делитель 1, то есть a, b -- взаимно просты

В другую:
Не существует числа x, где xa = 1 mod b. Умножая a на x мы будем получать различные остатки, по условию не равные 1. Возьмем минимальный из них xa и он будет делителем b, иначе мы можем взять остатки от zxa для разных z и получить остаток меньшe. Если он не будет делителем a, то мы можем получить элемент меньшe: z=1; пока zxa < a: z++, потом взяв (zx - 1)a. Значит есть какое-то число r != 1, которое является делителем a, b. Значит, они не взаимно просты.

2.2 Покажите, что для любых целых положительных n и b на отрезке [n, bn]
обязательно найдётся степень b.

Для всех n<=b в отрезке [n, bn] лежит b^1.

Возьмем n: b^x<n<=b^{x+1}:

Умножим все части на b:
b^{x+1}<bn<=b^{x+2}

Третья часть нас не интересует:
b^{x+1}<bn

Но n<=b^{x+1}:
n<=b^{x+1}<bn -> b^{x+1} лежит в [n, bn]

@279a1@279a1cbeaca54484a844da39fee9d829
наименьший остаток не равный 0

5.6. Докажите, что если веса всех рёбер неориентированного графа различ-
ны, то минимальное покрывающее дерево единственно.

Доказательство, что такое дерево единственное от обратного. Допустим, есть Т1 и Т2 -- минимальные покрывающие деревья. Все веса можно упорядочить по весу, потому что вес уникальный. И взять минимальное ребро e, которое есть только в одном дереве. Допустим оно в Т1. Если его добавить в Т2, то будет цикл. Возьмем все ребра цикла и уберем из него ребра, которые есть в T1. Все не могут быть в Т1, потому что иначе там тоже будет цикл. Значит есть какое-то еще ребро, которое есть в Т2, но нет в Т1. Но поскольку мы взяли минимальное отличное ребро, то мы можем в Т2 убрать из цикла ребро с большим весом, чем е и получить покрывающее дерево с меньшим весом, что противоречит условию.

5.10. Пусть T –– минимальное покрывающее дерево графа G, а H –– связный
подграф G. Покажите, что T ∩ H является частью некоторого минимального
покрывающего дерева графа H.

Надо доказать, что не может быть пересечения между Т и Н, что не входило бы в минимальное покрывающее дерева Н. Если пересечение не пусто, есть ребро e в Т = (v1, v2), где v1, v2 входят в H и это ребро не выходит в некоторое минимальное покрывающее дерево H, значит существует ребро (v2, v3) которое имеет меньший вес (иначе его можно было бы заменить на e). Но поскольку H подграф, то и в T можно заменить ребро и получить граф меньшего веса.

@6694b@6694bb9713d045bca91d81d1b7725241
кажется, по-другому надо как-то...

Забавный алгоритм для поиска длины периода последовательности 1/n в десятичном виде:

int period_length(int n) {
res = длина периода 1/n.

int l = 0;
int r = 1;

инвариант: r/n = результат отбрасывания
l знаков в 1/n.
while (l != n+1) {
r *= 10;
r = r % n;
l++;
}

(n+1)-ый член последовательности остатков.
auto c = r;
r *= 10;
r = r % n;
int k = 1;

// r = (n+k+1)-ый член последовательности.
while (r != c) {
r *= 10;
r = r % n;
k++;
}

return k;
}

Мы запоминаем n+1 знак последовательности и дальше ищем такой же знак, считая разные цифры. Потому что дробь выглядит как 0.(предпериод)(период) так вот длина предпериода не может превышать n. Потому что период начинается когда мы получаем один и тот же остаток при делении. А различных остатков меньше n.