Abstract Algebra: Theory and Applications

The code a % b will return the remainder upon division of $a$ by $b\text{.}$ In other words, the result is the unique integer $r$ such that (1) $0\le r<b\text{,}$ and (2) $a=bq+r$ for some integer $q$ (the quotient), as guaranteed by the Division Algorithm (Theorem 2.9). Then $(a-r)/b$ will equal $q\text{.}$ For example,

xxxxxxxxxx

r = 14 % 3

r

xxxxxxxxxx

q = (14 - r)/3

q

It is also possible to get both the quotient and remainder at the same time with the .quo_rem() method (quotient and remainder).

xxxxxxxxxx

a = 14

b = 3

a.quo_rem(b)

A remainder of zero indicates divisibility. So (a % b) == 0 will return True if $b$ divides $a\text{,}$ and will otherwise return False.

xxxxxxxxxx

(20 % 5) == 0

xxxxxxxxxx

(17 % 4) == 0

The .divides() method is another option.

xxxxxxxxxx

c = 5

c.divides(20)

xxxxxxxxxx

d = 4

d.divides(17)

The greatest common divisor of $a$ and $b$ is obtained with the command gcd(a, b), where in our first uses, $a$ and $b$ are integers. Later, $a$ and $b$ can be other objects with a notion of divisibility and “greatness,” such as polynomials. For example,

xxxxxxxxxx

gcd(2776, 2452)

We can use the gcd command to determine if a pair of integers are relatively prime.

xxxxxxxxxx

a = 31049

b = 2105

gcd(a, b) == 1

xxxxxxxxxx

a = 3563

b = 2947

gcd(a, b) == 1

The command xgcd(a,b)(“eXtended GCD”) returns a triple where the first element is the greatest common divisor of $a$ and $b$ (as with the gcd(a,b) command above), but the next two elements are values of $r$ and $s$ such that $ra+sb=gcd(a,b)\text{.}$

xxxxxxxxxx

xgcd(633,331)

Portions of the triple can be extracted using [ ](“indexing”) to access the entries of the triple, starting with the first as number 0. For example, the following should always return the result True, even if you change the values of a and b. Try changing the values of a and b below, to see that the result is always True.

xxxxxxxxxx

a = 633

b = 331

extended = xgcd(a, b)

g = extended[0]

r = extended[1]

s = extended[2]

g == r*a + s*b

Studying this block of code will go a long way towards helping you get the most out of Sage’s output. Note that = is how a value is assigned to a variable, while as in the last line, == is how we compare two items for equality.

The method .is_prime() will determine if an integer is prime or not.

xxxxxxxxxx

a = 117371

a.is_prime()

xxxxxxxxxx

b = 14547073

b.is_prime()

xxxxxxxxxx

b == 1597 * 9109

The command random_prime(a, proof=True) will generate a random prime number between $2$ and $a\text{.}$ Experiment by executing the following two compute cells several times. (Replacing proof=True by proof=False will speed up the search, but there will be a very, very, very small probability the result will not be prime.)

xxxxxxxxxx

a = random_prime(10^21, proof=True)

a

xxxxxxxxxx

a.is_prime()

The command prime_range(a, b) returns an ordered list of all the primes from $a$ to $b-1\text{,}$ inclusive. For example,

xxxxxxxxxx

prime_range(500, 550)

The commands next_prime(a) and previous_prime(a) are other ways to get a single prime number of a desired size. Give them a try below if you have an empty compute cell there (as you will if you are reading in the Sage Notebook, or are reading the online version). (The hash symbol, #, is used to indicate a “comment” line, which will not be evaluated by Sage. So erase this line, or start on the one below it.)

xxxxxxxxxx

# Practice area (not linked for Sage Cell use)

In addition to checking if integers are prime or not, or generating prime numbers, Sage can also decompose any integer into its prime factors, as described by the Fundamental Theorem of Arithmetic (Theorem 2.15).

xxxxxxxxxx

a = 2600

a.factor()

So $2600=2^3\times 5^2\times 13$ and this is the unique way to write $2600$ as a product of prime numbers (other than rearranging the order of the primes themselves in the product).

While Sage will print a factorization nicely, it is carried internally as a list of pairs of integers, with each pair being a base (a prime number) and an exponent (a positive integer). Study the following carefully, as it is another good exercise in working with Sage output in the form of lists.

xxxxxxxxxx

a = 2600

factored = a.factor()

first_term = factored[0]

first_term

xxxxxxxxxx

second_term = factored[1]

second_term

xxxxxxxxxx

third_term = factored[2]

third_term

xxxxxxxxxx

first_prime = first_term[0]

first_prime

xxxxxxxxxx

first_exponent = first_term[1]

first_exponent

The next compute cell reveals the internal version of the factorization by asking for the actual list. And we show how you could determine exactly how many terms the factorization has by using the length command, len().

xxxxxxxxxx

list(factored)

xxxxxxxxxx

len(factored)

Can you extract the next two primes, and their exponents, from a?

xxxxxxxxxx

# Practice area (not linked for Sage Cell use)