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.