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