File contents

# ======================================================================
# ====================      ARITMETICA MUDULAR      ====================
# ======================================================================

import time



# ======================================================================
# Calculo do mdc de dois inteiros
# (Funcao auxiliar)
# ======================================================================
def mdc(a,b):
    if a<0: a = -a
    if b<0: b = -b
    if a<b:
        temp = a
        a = b
        b = temp
    if b==0:
        return a
    else:
        return mdc(b,a%b)
# ----------------------------------------------------------------------




# ======================================================================
# Algoritmo euclideano estendido
# (Funcao auxiliar)
# ======================================================================
def mdcex(a,b): # par = [a,b]
    if a<0: a = -a
    if b<0: b = -b
    if a<b:
        temp = a
        a = b
        b = temp

    if a%b==0:
        return [0,1]
    
    else:
        x0, y0 = 1, 0
        x1, y1 = 0, 1
        r = a%b
        
        while r>0:
            q = a/b
            x, y = x0-q*x1, y0-q*y1
            x0, y0 = x1, y1
            x1, y1 = x, y
            a = b
            b = r
            r = a%b

    return [x,y]
# ----------------------------------------------------------------------



# ======================================================================
# Exponencial modular (a**b)mod n
# ======================================================================
def modpow(a,b,n):
    pow = 1
    pot = a%n
    if b==0:
        pass
    elif b>0:
        while b > 0:
            if b%2==1: pow = (pow*pot)%n
            pot = (pot*pot)%n
            b = b/2
    elif b<0:
        if mdc(a,n)==1:
            inverso = (mdcex(n,a%n)[1])%n
            if b==-1: pow = inverso
            else: pow = modpow(inverso,-b,n)
        else: pow = None
        
    return pow
# ----------------------------------------------------------------------



# ======================================================================
# Soma modular (a+b)mod n
# ======================================================================
def modsoma(a,b,n):
    return (a+b)%n
# ----------------------------------------------------------------------



# ======================================================================
# Diferenca modular (a-b)mod n
# ======================================================================
def moddife(a,b,n):
    return (a-b)%n
# ----------------------------------------------------------------------



# ======================================================================
# Produto modular (a*b)mod n
# ======================================================================
def modprod(a,b,n):
    return ((a%n)*(b%n))%n
# ----------------------------------------------------------------------



# ======================================================================
# Divisao modular (a/b)mod n
# ======================================================================
def moddiv(a,b,n):
    if mdc(b,n)==1:
        return (a*modpow(b,-1,n))%n
    else:
        return None
# ----------------------------------------------------------------------



# ======================================================================
# Verificar se uma string representa um inteiro
# (Funcao auxiliar)
# ======================================================================
def isint(s):
    try: 
        int(s)
        return True
    except ValueError:
        return False



# ======================================================================
# Menu principal
# ======================================================================
def menu():
    linhadupla = ''
    for i in range(70): linhadupla += '='
    print
    print linhadupla
    print '====================',
    print '     ARITMETICA MODULAR     ',
    print '===================='
    print linhadupla
    print
    print 'Escolha uma opcao:'
    print '------------------------------------'
    print '0 -> Encerrar o programa'
    print '1 -> Inteiros modulo n [a mod n]'
    print '2 -> Soma modulo n [(a+b) mod n]'
    print '3 -> Diferenca modulo n [(a-b) mod n]'
    print '4 -> Produto modulo n [(a*b) mod n]'
    print '5 -> Divisao modulo n [(a/b) mod n]'
    print '6 -> Potencia modulo n [(a^b) mod n]'
    print '------------------------------------'
    return raw_input('Opcao: ')
# ----------------------------------------------------------------------




# ======================================================================
# Menu operacoes
# ======================================================================
def operacoes(opcao):
    linhadupla = ''
    for i in range(70): linhadupla += '='
    print linhadupla
    # ------------------------------------------------------------------
    if opcao==1:
        print '==============',
        print 'INTEIROS MODULO n: Calculo de  a (mod n)',
        print '=============='
        print linhadupla
        print
        while True:
            a = raw_input('Informe o valor de a: ')
            if isint(a): break
            else: print 'O valor de "a" deve ser inteiro'
        while True:
            n = raw_input('Informe o valor de n: ')
            if (isint(n))and(int(n)>0): break
            else: print 'O valor de "n" deve ser inteiro positivo'
        print '{0} (mod {1}) = {2}'.format(a,n,int(a)%int(n))
    # ------------------------------------------------------------------
    if opcao==2:
        print '==============',
        print 'SOMA MODULO n: Calculo de (a + b)(mod n)',
        print '=============='
        print linhadupla
        print
        while True:
            a = raw_input('Informe o valor de a: ')
            if isint(a): break
            else: print 'O valor de "a" deve ser inteiro'
        while True:
            b = raw_input('Informe o valor de b: ')
            if isint(b): break
            else: print 'O valor de "b" deve ser inteiro'            
        while True:
            n = raw_input('Informe o valor de n: ')
            if (isint(n))and(int(n)>0): break
            else: print 'O valor de "n" deve ser inteiro positivo'
        print '({0} + {1}) (mod {2}) = {3}'.format(a,b,n,modsoma(int(a),int(b),int(n)))
    # ------------------------------------------------------------------
    if opcao==3:
        print '===========',
        print 'DIFERENCA MODULO n: Calculo de (a - b) (mod n)',
        print '==========='
        print linhadupla
        print
        while True:
            a = raw_input('Informe o valor de a: ')
            if isint(a): break
            else: print 'O valor de "a" deve ser inteiro'
        while True:
            b = raw_input('Informe o valor de b: ')
            if isint(b): break
            else: print 'O valor de "b" deve ser inteiro'            
        while True:
            n = raw_input('Informe o valor de n: ')
            if (isint(n))and(int(n)>0): break
            else: print 'O valor de "n" deve ser inteiro positivo'
        print '({0} - {1}) (mod {2}) = {3}'.format(a,b,n,moddife(int(a),int(b),int(n)))
    # ------------------------------------------------------------------
    if opcao==4:
        print '===========',
        print ' PRODUTO MODULO n: Calculo de (a * b) (mod n) ',
        print '==========='
        print linhadupla
        print
        while True:
            a = raw_input('Informe o valor de a: ')
            if isint(a): break
            else: print 'O valor de "a" deve ser inteiro'
        while True:
            b = raw_input('Informe o valor de b: ')
            if isint(b): break
            else: print 'O valor de "b" deve ser inteiro'            
        while True:
            n = raw_input('Informe o valor de n: ')
            if (isint(n))and(int(n)>0): break
            else: print 'O valor de "n" deve ser inteiro positivo'
        print '({0} * {1}) (mod {2}) = {3}'.format(a,b,n,modprod(int(a),int(b),int(n)))
    # ------------------------------------------------------------------
    if opcao==5:
        print '===========',
        print ' DIVISAO MODULO n: Calculo de (a / b) (mod n) ',
        print '==========='
        print linhadupla
        print
        while True:
            a = raw_input('Informe o valor de a: ')
            if isint(a): break
            else: print 'O valor de "a" deve ser inteiro'
        while True:
            b = raw_input('Informe o valor de b: ')
            if isint(b): break
            else: print 'O valor de "b" deve ser inteiro'            
        while True:
            n = raw_input('Informe o valor de n: ')
            if (isint(n))and(int(n)>1): break
            else: print 'O valor de "n" deve ser inteiro maior que 1'
        x = moddiv(int(a),int(b),int(n))
        if x==None: texto = '(Divisao impossivel)'
        else: texto = str(moddiv(int(a),int(b),int(n)))
        print '({0} / {1}) (mod {2}) = {3}'.format(a,b,n,texto)
    # ------------------------------------------------------------------
    if opcao==6:
        print '===========',
        print 'POTENCIA MODULO n: Calculo de (a ** b) (mod n)',
        print '==========='
        print linhadupla
        print
        while True:
            a = raw_input('Informe o valor de a: ')
            if isint(a): break
            else: print 'O valor de "a" deve ser inteiro'
        while True:
            b = raw_input('Informe o valor de b: ')
            if isint(b): break
            else: print 'O valor de "b" deve ser inteiro'            
        while True:
            n = raw_input('Informe o valor de n: ')
            if (isint(n))and(int(n)>0): break
            else: print 'O valor de "n" deve ser inteiro positivo'
        print '({0} ** {1}) (mod {2}) = {3}'.format(a,b,n,modpow(int(a),int(b),int(n)))

    




# ======================================================================
# Execucao
# ======================================================================
while True:
    opcao = ''
    while not(opcao in ['0','1','2','3','4','5','6']):
        for i in range(5): print
        opcao = menu()
    if int(opcao)==0:
        break
    else:
        print
        operacoes(int(opcao))
        print
        print 'Reiniciando: ',
        for i in range(28):
            print '.',
            time.sleep(0.1)