Math 440: Laboratory 1, Introduction to Abstract Algebra with SAGE

Introduction to SAGE and GAP:

Experiments in Abstract Algebra

Abstract:

This introduction is modeled after both Abstract Algebra with GAP by Julianne G. Rainbolt and Joseph A. Gallian, and after the worksheet provided by Project MOSAIC Joint Math Meetings Ancillary Workshop: Sage, Calculus, and Modeling by Karl-Dieter Crisman.

This worksheet was originally intended for Math 440: Introduction to Abstract Algebra, taught by Dr. Gwyn Whieldon at Hood College in Spring 2012. A pdf of the problems referenced in this worksheet is attached. Comments or questions should be sent to whieldon at hood dot edu.

Goals for Lab 1:

After completing this worksheet, students should be able to enter GAP and SAGE commands for:

• Logging in to Sage and starting a worksheet
• Changing to GAP mode, either in a specific frame or the whole worksheet
• Calculating gcd and lcm of integers x,y, and compute the minimal expression
  ax+by=\gcd(x,y)\;
• Calculations in modular arithmetic
  a\; \text{mod} \;n = b
• Calculations with Euler's Totient Function in Sage.

By the time you're on this page, you already will have a Sage notebook account. You will be submitting any computer portions of your homework to me through the Sage notebook interface, so having a user name which is easy for me to identify as you would help - but isn't vital.

First, click on the `File' drop-down menu above. Rename this worksheet YourLastNameFirstInitial_Lab1. For example, if this was my worksheet I would call it:

WhieldonG_Lab1

Just remember when you rename your file to use your last name, not MY last name.

In the upper right-hand corner, you'll see a `Share' button. Click on this and add whieldon as one of your collaborators. Your worksheet is now shared with me and this is how you will submit assignments to me. I'll leave comments in the worksheet itself in red when I grade them.

Preliminaries:

There are a number of functions which you can do directly in Sage. For example, if you'd like to compute 35!, you can use the command `factorial(35)'. Click in the box below with the command, and a blue `Evaluate' link should appear.

If you are in one of the open cells, the command `SHIFT-ENTER' also evaluates the box. To add a new box, place your mouse pointer below the output from the previous command until you see a blue bar. Clicking on it will add a new box below the current one wherever you are in the worksheet. To delete a box, delete all text in the box then use backspace. The box will disappear. Unfortunately, there is no `undo' if you accidentally delete a box, so be careful.

Sage can perform more basic calculations (addition, subtraction, multiplication, etc.) Try entering 5\ast (9+3) into the box below to see this.

Calculate 9^{50}.

Note that if you fail to include the final parenthesis, Sage will throw an error. Try running the following command to see this type of output.

On a useful note, you can automatically complete the parenthesis above by putting your cursor at the end of the line, then using the command `CTRL-0' (in this case, twice.)

Euclidean Algorithm:

Let's see how Sage and GAP can speed up problems like those you worked on for your homework. Problem Set 1 began with:

1. For each of the following pairs of integers a and b, determine their greatest common divisor, their least common multiple, and write their greatest common divisor in the form ax+by for some integers x and y.

(a) a=20 and b=13

(b) a=69 and b=372

(c) a=792 and b=275

(d) a=11391 and b=5673

(e) a=1761 and b=1567

(f) a=507885 and b=60808

Problem source: Dummit and Foote, Abstract Algebra.

Let's see how to answer part (a) using GAP.

(a) a=20 and b=13

To use commands from GAP in one section of your worksheet, start it with `%gap'. To calculate the greatest common denominator for a pair of integers a and b, use the command `Gcd(a,b)'. Capitalization is important.

If you'd like to use more than one command in a given box, end each line with a semicolon:

Calculate the greatest common denominator for the remaining pairs in the box above.

To answer the second half of the question, we can use another command, `Gcdex', short for `extended greatest common denominator.'

Note that this also told us that gcd(20,13)=1, and the two outputs `coeff1' and `coeff2' are exactly the x and y we need for

The `coeff3' and `coeff4' are the minimal x and y such that

Calculate the expressions for the rest of the parts of the problem in the following box:

On a final note before moving on, the command `Lcm' can be used to compute the least common multiple of a and b as well:

Modular Arithmetic:

GAP can perform modular arithmetic. For example:

Careful: Blank spaces are needed around `mod'. If you type 23mod6 into GAP, it will interpret it as a symbol rather than a function. See the following for an example.

With this in mind, answer the following questions from the homework using GAP:

2. Compute the following:

(a) The remainder when 37^{100} is divided by 29.

(b) The last two digits of 9^{1500}.

Euler's Totient Function:

Recall from the homework:

6. The Euler \phi-function is defined as follows: for n\in{\mathbb Z}^+, let \phi(n) be the number of positive integers a\leq n with a relatively prime to n. For example, \phi(12)=4, because 1,5,7, and 11 are the only positive integers less than or equal to 12 which have no factors in common with 12.

We could use Sage to quickly calculate \phi(p) for a number of different primes.

What's your conjecture for a formula for \phi(p) for primes now?

To guess at a more general formula for \phi(n), we could use Sage to do some more experimentation.

We'll return to Euler's \phi function in a later class.