Teorema Euler dan Pangkat Modular Bagian 2

Apa yang akan kita kerjakan hari ini? (1) Hubungan Modular dengan Teorema Euler dan Bezout’s Lemma; (2) Mencari (a mod m = n), dengan (euler_phi(m)) dan Bezout’s Lemma.

Sebelumnya Bagian 1

# [?] 27**41 % 77

# Apakah
print 27**60 % 77 == 1
# True

import fractions

def euler_phi(n):
    amount = 0
    for k in range(1, n + 1):
        if fractions.gcd(n, k) == 1:
            amount += 1
    return amount

print euler_phi(77) == 60
# True

# Teorema Euler
# a**et(n) % n = 1

# Apakah
print euler_phi(7*11) == (7-1)*(11-1) == euler_phi(77)
# True

print 27**41 % 77 == ((27**10) * (27**10) * (27**10) * (27**10) * (27**1)) % 77 == 1 * 1 * 1 * 1 * 27 == 27
# True

# PART I-sub
'''
a % m = r1
a % n = r2
gcd(m,n) = 1    =>    r2(m*x) + r1(n*y) % (m*n) = jawaban

a, r1, r2 elemen Z
m, n elemen N+

Dimana m*x + n*y = 1 for x, y elemen Z    # Bezout's Lemma
'''

'''
x, y, m, n, r1, r2 = 2, -3, 11, 7, 5, -1

a % 11 == 5
a % 7 == -1
gcd(11,7) == 1
=> -1(11*2) + 5(7*(-3)) == -127
=> -127 % 77 == 27

a, 5, (-1) elemen Z
11, 7 elemen N+

Dimana 11 * (2) + 7 * (-3) = 1
'''

from fractions import gcd

# Apakah
print gcd(11,7) == 1
# True

# Apakah
print -1*(11*2) + 5*(7*(-3)) == -127
# True

# Apakah
print -127 % 77 == 27
# True

# Apakah
print 11*(2) + 7*(-3) == 1
# True

x, y, m, n, r1, r2 = 2, -3, 11, 7, 5, -1
print x, y, m, n, r1, r2

# Apakah
print gcd(m,n) == 1
# True

# Apakah
print r2*(m*x) + r1*(n*(y)) == -127
# True

# Apakah
print -127 % 77 == 27
# True

# Apakah
print m*x + n*y == 1
# True
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s