25 // 7, 25 % 7

-17 // 8, -17 % 8

"""
Explanation: Copyright 2021 Google LLC
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
Instructions
The notebook linked to in the go link above is view-only.  Make your own personal copy by selecting "File > Save a copy in Drive", because the exercises are to modify the code snippets.
To execute code snippets, click the "play" button on the left edge of each code box.  You can also use the "runtime" menu above if you need to run many code boxes at once.
Introduction
One of the core examples in both the lectures and exercise sessions has been the integers mod n, in both their additive and multiplicative forms.  In this brief colab, we will walk through implementations of basic, but critical, algorithms for doing calculations in $(\Bbb Z/n\Bbb Z)$.  This material slightly diverges from abstract algebra into the realm of (computational) elementary number theory, although the Euclidean algorithm plays a substantial role in ring theory.
The Euclidean Algorithm: Computing gcds
Recall that the greatest common divisor (gcd) of two integers a and b is the largest positive integer that divides both a and b. We have already seen the notion of coprime or relatively prime (namely, gcd(a, b) = 1) come up when identifying the elements of $(\Bbb Z/n\Bbb Z)^{*}$.
A very old, classical algorithm, named the Euclidean algorithm, for calculating gcds was known to the ancient Greeks.  The algorithm is based on the following basic property of gcds:
Exercise.  Suppose a, b are integers. Then gcd(a, b) = gcd(a, a+b).  More generally for any integer n, gcd(a, b + na) = gcd(a, b).  (Note that gcd(a, a+nb) != gcd(a, b) in general, though.)
Recall from grade school the operation of division with remainder.  Given an integer a and a positive integer b, the division with remainder of a divided by b (sometimes called Euclidean division) is the unique pair (q, r) of integers satisfying
$a = qb + r$
where $0 \leq r < b$.  q is called the quotient and r the remainder.  (Homework exercise: prove that this pair exists and is unique.)
Of course, b divides a exactly when r = 0.
In Python 3, you can find q and r via the  // and % operations:
End of explanation
"""


# Exercise. Implement the Euclidean algorithm.
# Inputs: two integers, a, b, possibly zero or negative.
# If a = b = 0, this function should return an error.
# (Feel free to return an error for non-integer values as well.)
# Output: the (positive) gcd of a, b.
# Test your implementation using the test cases below.
def gcd(a,b):
  # Fill in your implementation here
  return 0

# Test cases for gcd above. If the tests pass, there will be no output; if they fail, you will see the failed cases printed out.
testcases = [
             (24, 15, 3),
             (15, 24, 3),
             (0, 5, 5),
             (5, 0, 5),
             (-17, 8, 1),
             (27593, 1990, 1),
             (58392001839363215960304, 639201033321384, 24)
            ]
for (a, b, g) in testcases:
  got = gcd(a, b)
  if got != g:
    print(f"got gcd({a}, {b}) = {got}, want {g}")

"""
Explanation: The Euclidean algorithm is the insight that repeated Euclidean divisions can be used to compute a gcd. Suppose we want to compute gcd(a, b).  We can assume a, b are both positive, and a > b.  Then:

Compute the Euclidean division of a by b: suppose $a = q_{1}b + r_{1}$. 
If $r_{1} = 0$, then $b | a$ and gcd(a, b) = b; the algorithm is over.
Otherwise: Compute the Euclidean division of b by $r_{1}$: $b = q_{2}r_{1} + r_{2}$.
If $r_{2} = 0$, then we claim $r_{1}$ is gcd(a, b).  If $r_{2} > 0$, repeat this Euclidean division with $r_{1}$ divided by $r_{2}$.
This process gives a sequence of remainders $r_{1}, r_{2}, ..., r_{n}, r_{n+1} = 0$  Because $r_{1} > r_{2} > ...$, this process must eventually terminate.  We claim that $r_{n}$ is gcd(a, b).

Before sketching why this algorithm is correct, let's look at an example:
gcd(2376, 711):

2376 = 3 * 711 + 243, so $q_{1} = 3, r_{1} = 243$.
711 = 2 * 243 + 225, so $q_{2} = 2, r_{2} = 225$.
243 = 1 * 225 + 18, so $q_{3} = 1, r_{3} = 18$.
225 = 12 * 18 + 9, so $q_{4} = 12, r_{4} = 9$.
18 = 9 * 2 + 0, so $q_{5} = 9, r_{5} = 0$, and gcd(236, 711) = 9.

Why is the Euclidean algorithm correct?  It goes back to the basic property above: because $a = q_{1} * b + r_{1}$, then $\gcd(a, b) = \gcd(b, r_{1})$. And similarly, $\gcd(r_{i}, r_{i+1}) = \gcd(r_{i+1}, r_{i+2})$, so we find that 
$\gcd(a, b) = \gcd(b, r_{1}) = ... = \gcd(r_{n-1}, r_{n}) = r_{n}$.
End of explanation
"""


# Exercise: implement the extended Euclidean algorithm
# Input: two integers a, b.
# If both inputs is zero, return an error.
# Output: an ordered triple of integers (x, y, g), where g = gcd(x, y) and  ax + by = g.
def bezout(a, b):
  # Fill in your implementation here
  return 0, 0, 0
  


# Test cases for bezout above. If the tests pass, there will be no output; if they fail, you will see the failed cases printed out.
testcases = [
             (24, 15, 3),
             (15, 24, 3),
             (-17, 8, 1),
             (27593, 1990, 1),
             (58392001839363215960304, 639201033321384, 24) 
            ]
for (a, b, g) in testcases:
  x, y, got_gcd = bezout(a, b)
  if got_gcd != g:
    print(f"got gcd({a}, {b}) = {got_gcd}, want {g}")
    continue
  if a * x + b * y != g:
    print(f"bezout({a}, {b}) = ({x}, {y}), but {a} * {x} + {b} * {y} = {a*x+b*y}, not {g}")

"""
Explanation: Notice that the last test case is quite large, and yet your implementation (hopefully) calculated the answer quickly.  As a homework exercise, do a O-time complexity analysis of the Euclidean algorithm, keeping in mind the following:

For arithmetic operations, it is typical for the "n" which measures input size to be the number of digits of the input, not the actual input itself.
With this convention in mind, ordinary addition is $O(n)$, while grade-school multiplication is $O(n^{2})$.  (A <a href="https://hal.archives-ouvertes.fr/hal-02070778">very recent paper</a> gives a $O(n \log n)$ algorithm for multiplication, which is the culmination of a century of work in fast multiplication algorithms.)
A naive Euclidean division takes $O(n^{2})$ time.

Of course, there are ways to optimize this algorithm to go faster than the naive, straightforward implementation.
The Extended Euclidean Algorithm: Bezout's Identity
If gcd(a, n) = 1, we can also use the Euclidean algorithm to find the inverse of a mod n.  Recall that the inverse of a mod n is the element $a^{-1}$ of $(\mathbb{Z}/n\mathbb{Z})^*$ such that $a * a^{-1} \equiv 1 \mod n$.  In other words, we are looking for some integer $x$ such that $a * x + n * q = 1$ for some integer q.
This is a specific example of a more general problem: given fixed integers a, b, and d, to determine when there exists a pair of integers (x, y) solving
ax + by = d.
The answer is completely given by the gcd:
Proposition.  ax + by = d has integer solutions (x, y) if and only if $\gcd(a, b) | d$.
One direction of the implication is easy to show: if ax + by = d is true for some integers x, y, because gcd(a, b) divides both a and b, it is the case that gcd(a, b) divides both ax and by, and hence ax + by = d.
The other direction is shown by providing an explicit algorithm, called the extended Euclidean algorithm, which computes a pair (x, y) which solves ax + by = d.
The basic idea is as follows: in the sequence of Euclidean divisions in the Euclidean algorithm, we have a bunch of equations of the form 
$r_{i-1} = q_{i+1} * r_{i} + r_{i+1}$,
which eventually terminate when $r_{n+1} = 0$.  
The second-to-last equation is
$r_{n-2} = q_{n} * r_{n-1} + r_{n}$.
Note we can rewrite this as
$r_{n} = r_{n-2} * 1 + r_{n-1} * (-q_{n})$.
The point of this expression is that we have expressed $r_{n} = \gcd(a, b)$ as an integer linear combination of $r_{n-2}$ and $r_{n-1}$, and the key insight is that we can use the prior Euclidean division to rewrite $r_{n-1}$ as an integer linear combination of $r_{n-2}$ and $r_{n-3}$, and then substitute that into this equation with $r_{n}$ to express $r_{n}$ as an integer linear combination of $r_{n-2}$ and $r_{n-3}$.  Explicitly, this looks like:
$r_{n-1} = r_{n-3} * q_{n-2} + r_{n-2}$, so
$r_{n} = r_{n-2} * 1 + (r_{n-3} * q_{n-2} + r_{n-2}) * (-q_{n}) = r_{n-3} * (q_{n-2} * -q_{n}) + r_{n-2} (1 - q_{n})$.
We can repeatedly "back-substitute" to progressively express $r_{n}$ as integer linear combinations of $r_{i+1}$ and $r_{i}$ for $i = n-2, n-3, ...$ until we reach a and b.
Example.  From the test cases we know that gcd(24, 15) =  3. Let's find integers (x, y) such that 24x + 15y = 3.
The Euclidean algorithm steps are:

24 = 1 * 15 + 9
15 = 1 * 9 + 6
9 = 1 * 6 + 3
6 = 3 * 2 + 0

Backtracking from the second-to-last of these, we get:

3 = 9 + 6 (-1)
3 = 9 + (15 - 9) * (-1) = 15 (-1) + 9 (2)
3 = 15 * -1 + (24 - 15) * 2 = 24 (2) + 15 (-3)

So (x, y) = (2, -3) solves 24x + 15y = 3.
From an algorithmic standpoint, it is not ideal to have to keep in memory the result of every subsequent Euclidean division and then "rewind" them at the end.  So from the standpoint of implementation, it is easier to instead keep track of quantities which can be updated iteratively.  The key is to notice that at the $i$th Euclidean division, it is possible to iteratively compute integers $(x_{i}, y_{i})$ which solve $a x_{i} + b y_{i} = r_{i}$, by using the results of the $i$th division along with $(x_{i-1}, y_{i-1})$ and $(x_{i-2}, y_{i-2})$:

$a* x_{i-1} + b * y_{i-1} = r_{i-1}$,
$a * x_{i-2} + b * y_{i-2} = r_{i-2}$,
$r_{i-2} = q_{i} * r_{i-1} + r_{i}$,

together imply that
$r_{i} = a * x_{i-2} + b * y_{i-2} - q_{i} (a * x_{i-1} + b * y_{i-1}) = a(x_{i-2} - q_{i} * x_{i-1}) + b (y_{i-2} - q_{i} y_{i-1})$
so $(x_{i}, y_{i}) = (x_{i-2} - q_{i} * x_{i-1}, y_{i-2} - q_{i} * y_{i-1})$.
The identity $ax + by = \gcd(a, b)$ is often called Bezout's identity.
Example. Let's rework the 24, 15 example using this approach.

24 = 1 * 15 + 9
9 = 24 (1) + 15 (-1)
15 = 1 * 9 + 6
6 = 15 - 1 * 9 = 15 - (24 - 15) = 24 (-1) + 15 (2)
9 = 1 * 6 + 3
3 = 9 - 6 = (24(1) + 15(-1)) - (24(-1) + 15(2)) = 24(2) + 15(-3)
End of explanation
"""


bezout(346, 5711)

"""
Explanation: Going back to the original question of computing multiplicative inverses in integers mod n, we can just call this bezout function.  For example, for the prime $p = 5711$, to get the inverse of 346, call bezout(346, 5711):
End of explanation
"""


