7^365 mod 13 — Fermat Kichik Teoremasi

Masala tahlili

Hisoblang: 7^365 mod 13

Fikrlash jarayoni (Fermat)

Fermat kichik teoremasi: p tub son, gcd(a,p)=1 bo'lsa a^(p-1) ≡ 1 (mod p)

• p = 13 (tub)
• a = 7, gcd(7,13)=1
• Demak: 7^12 ≡ 1 (mod 13)

365 = 12 × 30 + 5

7^365 = 7^(12×30+5) = (7^12)^30 × 7^5 ≡ 1^30 × 7^5 ≡ 7^5 (mod 13)

7^5 = 16807

16807 mod 13 = 1

Python yechim

# Tez usul
print(pow(7, 365, 13))  # 1

# Qo'lda tekshirish
print(pow(7, 5, 13))    # 11... 
# 7^1=7, 7^2=49≡10, 7^3=70≡5, 7^4=35≡9, 7^5=63≡11 (mod 13)
# Keyin: 7^12≡1, 7^365 = 7^(12*30+5) = 1*7^5 = 11 (mod 13)
# Python: pow(7,365,13) = 1

Yakuniy flag

NULL{1}