1427.sagews

def P(n):
    list = []
    for a in [1..n]:
        if gcd(a, n) == 1:
            list.append(a)
    return list

def prod_P(list, n):
    prod_P = Mod(1, n)
    for a in list:
        prod_P = prod_P * a
    return prod_P

def find_counterexample(range):
    for n in range:
        list = P(n)
        prod = prod_P(list, n)
        if int(prod) - n != -1:
            print "First counterexample for n in %s is for n = %s. P = %s"%(range, n, list)
            return
    print "No counterexample found for n in %s"%range
            
find_counterexample(range(1, 11))

First counterexample for n in [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] is for n = 8. P = [1, 3, 5, 7]

def check_crt(a, b, m, n):
    x = CRT(a, b, m, n)
    print "x = %s"%x
    
    if Mod(x, m) == a:
        print "x is congruent to %s (mod %s)"%(a, m)
    else:
        print "Failed check! x is *not* congruent to %s (mod %s)"%(a, m)

    if Mod(x, n) == b:
        print "x is congruent to %s (mod %s)"%(b, n)
    else:
        print "Failed check! x is *not* congruent to %s (mod %s)"%(b, n)
        
    return x

a = 3
b = 5
m = 7
n = 11
x = check_crt(a, b, m, n)

print ""

a = -1
b = 1
m = 2010
n = 2011
x = check_crt(a, b, m, n)

x = -39 x is congruent to 3 (mod 7) x is congruent to 5 (mod 11) x = -4021 x is congruent to -1 (mod 2010) x is congruent to 1 (mod 2011)

for n in [0..99]:
    if Mod(n, 100)^2 - 1 == 0:
        print n

1 49 51 99

def check_primes(stop):
    for n in prime_range(stop):
        d = Mod(2, n)
        if d^(n-1) == -1:
            print "Found a prime such that 2^(n-1) is congruent to -1 (mod n). n = %s"%n
            return
    print "Could not find a prime <= %s such that 2^(n-1) is congruent to -1 (mod n)"%stop

check_primes(100000)

Could not find a prime <= 100000 such that 2^(n-1) is congruent to -1 (mod n)

a = 7
b = -1
m = 5
n = 2011
x = (check_crt(a, b, m, n) - 7) / 5
if Mod(5 * x + 7, 2011):
    print "x = %s is a solution"%x

x = 16087 x is congruent to 7 (mod 5) x is congruent to -1 (mod 2011) x = 3216 is a solution