Abstract Algebra: Theory and Applications

Subsection Division Algorithm

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\leq r\lt 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,

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

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

The .divides() method is another option.

Subsection Greatest Common Divisor

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,

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

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{.}\)

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.

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.

Subsection Primes and Factoring

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

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.)

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

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.)

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).

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.

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().

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