Теория чисел и элементы криптографии (Контрольная №4, Числовые сравнения)

1. Найдите остатки от деления:

а) 235+3541 на 13;

б) 361-249 на 17;

в) 3575+47100 на 132;

г) 3273+2373 на 9.

2. Докажите, что 100-я степень любого целого числа либо делится на 125, либо при делении на 125 дает остаток, равный 1.

3. Докажите, что если (а, 10)=1, то 10100n+1 ≡ a (mod 1000), где n  N.

4. Докажите, что если (п, 5)=1, то п2 ≡ l (mod 24).

1. Найдите остатки от деления:

а) 235+3541 на 13;

б) 361-249 на 17;

в) 3575+47100 на 132;

г) 3273+2373 на 9.

2. Докажите, что 100-я степень любого целого числа либо делится на 125, либо при делении на 125 дает остаток, равный 1.

3. Докажите, что если (а, 10)=1, то 10100n+1 ≡ a (mod 1000), где n  N.

4. Докажите, что если (п, 5)=1, то п2 ≡ l (mod 24).