2745.sagews

# Divisibility
# does 3 divide 2^15 - 1?
3.divides(2^15-1)

False

# Greatest Common Divisors
gcd(24, 12345)

3

# Extended GCD
xgcd(10, 52)

(2, -5, 1)

# This means that 2 = (-5)*10 + 1*(52)

# Modular Arithmetic
Mod(100, 34)
# gives 100 mod 34

32

# a^n mod m
# 2^100 mod 10
power_mod(2, 100, 10)

6

# Multiplicative inverses
# To find the inverse of 3 mod 100:
inverse_mod(3, 100)
# Note: we know 3 * 33 = 99 = -1 mod 100
#       so 3 *(-33) = -99 = 1 mod 100

67

# What if we try to find the inverse of 2 modulo 100?
inverse_mod(2, 100)

Traceback (most recent call last): File "<stdin>", line 1, in <module> File "_sage_input_8.py", line 10, in <module> exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("IyBXaGF0IGlmIHdlIHRyeSB0byBmaW5kIHRoZSBpbnZlcnNlIG9mIDIgbW9kdWxvIDEwMD8KaW52ZXJzZV9tb2QoMiwgMTAwKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in <module> File "/tmp/tmpbSnUXy/___code___.py", line 3, in <module> exec compile(u'inverse_mod(_sage_const_2 , _sage_const_100 )' + '\n', '', 'single') File "", line 1, in <module> File "/usr/local/sage2/local/lib/python2.6/site-packages/sage/rings/arith.py", line 1740, in inverse_mod return a.inverse_mod(m) File "integer.pyx", line 5155, in sage.rings.integer.Integer.inverse_mod (sage/rings/integer.c:28828) ZeroDivisionError: Inverse does not exist.

#Chinese Remainder Theorem
# To solve x = a mod m and x = b mod n
# Example  x = 2 mod 11 and x = 3 mod 13
crt(2, 3, 11, 13)

68

# Check:
mod(68, 11)

2

mod(68, 13)

# Factoring is useful (and hard!)
factor(1234567)

127 * 9721

# Primality Testing
is_prime(987654321)
# What algortihm does sage use?  Look it up, it's open source.

False

#Sometimes we want to find a big prime:
next_prime(2^40)

1099511627791

# Or the nth prime
nth_prime(10)

541

# primitive roots  -- find a primitive root modulo 37
r = primitive_root(37)
r

2

# check that the order is correct 
Mod(r, 37).multiplicative_order()

36

Mod(31, 37).multiplicative_order()

4