integers-sage.ipynb

Kernel:

%%html
<link href="http://mathbook.pugetsound.edu/beta/mathbook-content.css" rel="stylesheet" type="text/css" />
<link href="https://aimath.org/mathbook/mathbook-add-on.css" rel="stylesheet" type="text/css" />
<style>.subtitle {font-size:medium; display:block}</style>
<link href="https://fonts.googleapis.com/css?family=Open+Sans:400,400italic,600,600italic" rel="stylesheet" type="text/css" />
<link href="https://fonts.googleapis.com/css?family=Inconsolata:400,700&subset=latin,latin-ext" rel="stylesheet" type="text/css" /><!-- Hide this cell. -->
<script>
var cell = $(".container .cell").eq(0), ia = cell.find(".input_area")
if (cell.find(".toggle-button").length == 0) {
ia.after(
    $('<button class="toggle-button">Toggle hidden code</button>').click(
        function (){ ia.toggle() }
        )
    )
ia.hide()
}
</script>

Important: to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the "Run" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard.

ParseError: KaTeX parse error: \newcommand{\lt} attempting to redefine \lt; use \renewcommand

Section2.6Sage

¶

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\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,

r = 14 % 3
r

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

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.

(20 % 5) == 0

(17 % 4) == 0

The .divides() method is another option.

c = 5
c.divides(20)

d = 4
d.divides(17)

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,

gcd(2776, 2452)

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

a = 31049
b = 2105
gcd(a, b) == 1

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{.}$

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.

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.

SubsectionPrimes and Factoring

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

a = 117371
a.is_prime()

b = 14547073
b.is_prime()

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

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

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,

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

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

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.

a = 2600
factored = a.factor()
first_term = factored[0]
first_term

second_term = factored[1]
second_term

third_term = factored[2]
third_term

first_prime = first_term[0]
first_prime

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

list(factored)

len(factored)

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