# Section2.6Sage¶ permalink

Many properties of the algebraic objects we will study can be determined from properties of associated integers. And Sage has many powerful functions for analyzing integers.

# SubsectionDivision Algorithm

The code `a % b` will return the remainder upon division of \(a\) by \(b\). In other words, the result is the unique integer \(r\) such that (1) \(0\leq r\lt b\), 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\). 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\), and will otherwise return `False`.

The `.divides()` method is another option.

# SubsectionGreatest 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)\).

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

# SubsectionPrimes 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\). 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\), 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`?