# Math 310: Congruences Using SageMath xgcd()

## 0. Otherview

This interactive worksheet looks at solving congruences with the help of
the idea that a greatest common divisor of two integers can be written as a
linear combination of the two integers. It also helps to have
the *Extended Euclidean Algorithm* available using the
SageMath *xgcd()*.
### Using SageMath Cells

You will find *SageMath Cells* in this worksheet. Some include code
that demonstrates SageMath functions and syntax. Some that generate the
constants (\(a, b, p, q\)) that will setup the questions you will answer.

For each of the 4 SageMath Cells in this section:

- Read the comment above the Cell.
- Click the
*Evaluate* button
- Observe the output in the output box.
- Explain the Cell results to your notebook or another person at your table.

1. Notice the output: By default, SageMath only echos the value of the last line.

2. You can use *print* statements to get more feedback.

3. *xgcd()* and *mod()* are two functions you can use.

4. Note: The results of each executed cell are passed on to the cells
below. The results are lost every time you reload the web page.

### Take notes as you work through these the two questions

Everything you enter will be lost when you reload this web page.
You should take notes as you go along.

## 1. Solving a congruence

Select a random integer \(a\) in the range of 1000 to 2000. Use \(a\) to pick
the \(a^{th}\) prime number

### Question 1

Use the *xgcd()* function to solve the
congruence: \[a \cdot x \equiv 1 \bmod p\]
using the values of \(a\) and \(p\) selected above.
Here are two Cells to use for code to answer question 1:

Use this SageMath Cell to demonstrate that your numeric answer is correct.

## 2. Solving a pair of simultaneous congruences

We have \(a\) and \(p\) from question 1, so get \(b\) and \(q\) the same way.

### Question 2

Solve:

\(x \equiv a \bmod p \\ x \equiv b \bmod q \)

using the values of \(a, b, p\) and \(q\) selected above.

#### Notebook Comment For Question 2

How do you know there will be a solution? Write the complete question and your reasoning in your notebook.

Here are two Cells to use for code to answer question 2:

Use this SageMath Cell to demonstrate that your numeric answer is correct.

This page last modified
Fri Oct 5 11:01:06 PDT 2018
bic - turing