Теореми на Ферма , Ойлер и Уилсън

[Гост]

Здравейте!
Имам затруднение със следната задача:
Да се намерят последните две цифри на числото 3 на степен "а" , където "а"= 2030014966

[peyo]

Здравейте!
Имам затруднение със следната задача:
Да се намерят последните две цифри на числото 3 на степен "а" , където "а"= 2030014966

Не зная кои теореми на господата Ферма , Ойлер и Уилсън има предвид автора, но това няма да ни спре да решим задачата, защото ние няма да използваме теореми.

Да видим какво става с последните 2 цифри на числото 3 когато последователно с натрупване го умножаваме с 3:

In [143]: for i in range(3,70): q = 3**i; print(i,str(q)[-2:], sep=": ", end =", ")

3: 27, 4: 81, 5: 43, 6: 29, 7: 87, 8: 61, 9: 83, 10: 49, 11: 47, 12: 41, 13: 23, 14: 69, 15: 07, 16: 21, 17: 63, 18: 89, 19: 67, 20: 01, 21: 03, 22: 09,
23: 27, 24: 81, 25: 43, 26: 29, 27: 87, 28: 61, 29: 83, 30: 49, 31: 47, 32: 41, 33: 23, 34: 69, 35: 07, 36: 21, 37: 63, 38: 89, 39: 67, 40: 01, 41: 03, 42: 09,
43: 27, 44: 81, 45: 43, 46: 29, 47: 87, 48: 61, 49: 83, 50: 49, 51: 47, 52: 41, 53: 23, 54: 69, 55: 07, 56: 21, 57: 63, 58: 89, 59: 67, 60: 01, 61: 03, 62: 09,
63: 27, 64: 81, 65: 43, 66: 29, 67: 87, 68: 61, 69: 83,

Колко интересн! Намерихме повтярящ се цикъл с дължина 20 елемента, започвайки от $3^3$ като първото двуцифрено число:
27, 81, 43, 29, 87, 61, 83, 49, 47, 41, 23, 69, 07, 21, 63, 89, 67, 01, 03, 09

Сега това число 2030014966 трябва да разберем на кой индекс от 20-те елемента ще се спре? Вероятно ще е нещо свързано с остатък при деление на 20. Да използваме математическо налучкване:

Ако за $a$ вместо 2030014966 имахме например 35 трябва да върнем 07, което е 13-тия елемент от намерения цикъл.

In [152]: 35 %20
Out[152]: 15

Даде ни 15 а на нас ни трябва 13. Може би тогава формулата е:

$a \% 20 -2$

Да проверим за 57 например. Трябва да върне 63, което е 15 елемент.

In [156]: (57 % 20) -2
Out[156]: 15

Ок, намерихме формулата която търсим. Да видим за 2030014966 :

In [159]: (2030014966 % 20) -2
Out[159]: 4

4-тия елемнт от нащия списък е:
29

С което задачата е решена.