Learn the definition of congruences, the properties they contain, and the procedures for solving them.

Congruences: Lesson

Now that we have these three properties of congruences defined, we are better prepared for when we need to solve congruence problems! There are three distinct congruence problem types based on which variable in the expression:

```tex
a \equiv b\;(mod\;n)
```

is unknown:

1. Suppose only `a` is unknown. Then, from the definition of congruence, we have `(a-b) = n*k`, or `a = n*k + b`. This means that the answers we seek are all values of `a` for which `n` divides `a-b`, or equivalently all values of `a` for which `a-b` is a multiple of `n`.
2. Suppose only `b` is unknown. In this case, the procedure for solving for `b` is identical to the procedure for solving for `a` because we proved the symmetric property of congruences!
3. Suppose only `n` is unknown. Then, since `(a-b) = n*k` by definition of congruence, we are seeking an integer `k` in which `(a-b)/n` is an integer. In other words, we must find all positive integers `n` such that `n` divides `(a-b)`. This is equivalent to finding every factor of `(a-b)` since they all divide `(a-b)` with no remainder. 

Thankfully, since we have only three variables present in any given congruence, these three scenarios are the only ones possible (assuming that only one of these three variables is unknown). These next few checkpoints will hopefully boost your confidence in your ability to solve simple congruence problems!


Solving Simple Congruence Problems

We only have one more property left to show! This final congruence property is called the _transitive property_, the statement of which goes like this:

Suppose we have the integers a, b, c, and n already defined with n > 0. If a is congruent to b mod n and b is congruent to c mod n, then it must be true that a is congruent to c mod n.

To prove the transitive property, we first suppose that a is congruent to b mod n and that b is congruent to c mod n. By definition of congruence, there exists an integer `k` such that `(a-b) = n*k`, and there exists another integer `m` such that `(b-c) = n*m`. Our task is to show that n divides (a-c), or that there exists some integer such that (a-c) is equal to n times that integer. But,

```tex
(a-c) = a-b+b-c = (a-b) + (b-c)
```

and so, from the congruence definitions we made above,

```tex
(a-b) + (b-c) = nk + nm = n(k + m)
```

We know that `k + m` is an integer because the sum of two integers is an integer. Therefore, we have shown that n divides (a-c), which proves that a is congruent to c mod n. We will use Python to prove the transitive property of congruences through multiple checkpoints. 


The Transitive Property of Congruences

Now we will transition into discussing some simple properties that congruences have. We begin by defining the idea that _x relates to y_ if a relationship between inputs `x` and output `y` exists. (_Functions_, as you may recall from basic algebra, are a special kind of relation in which our input `x` has at most one output `y`.) We can define the relation for congruences like so: for integers a, b, and n with n > 0, a relates to b if a is congruent to b mod n. 

We can now use this relation to define three congruence properties, the first of which is the reflexive property. The _reflexive property_ states that a relates to a, or that a is congruent to a mod n for integers a and n with n > 0. To see this, we use the definition of congruence to write out that n divides `a - a`, or 0. This is always true since 0 is divisible by every integer excluding 0, which n cannot be. Therefore, congruence is a reflexive relation. We can use Python to verify the reflexive property for congruences quite easily.


The Reflexive Property for Congruences

Congratulations, you have reached the end of this lesson! Let’s recap what we learned:

- We say that, for integers a, b, and n with n > 0, _a is congruent to b mod n_ if n divides (a-b). Equivalently, a is congruent to b mod n if there exists some integer k for which `a-b = n*k` is true. We write this mathematically as:

```tex
a \equiv b\;(mod\;n)
```

- The _reflexive property_ for congruences states that a is congruent to a mod n.

- The _symmetric property_ for congruences states that, if a is congruent to b mod n, then b is congruent to a mod n.

- The _transitive property_ for congruences says that, if a is congruent to b mod n and b is congruent to c mod n, then a is congruent to c mod n

- We can solve for congruences and linear congruences using a procedure that is analogous to solving for the variable `x` in a linear equation. The only differences are that congruences must perform modular arithmetic after each step and that the solution of a congruence problem has many possibilities for the value of the unknown variable.

Congruences Review

Here is a problem people face at work: suppose a team of four must complete a three-task project. Everyone decides to assign the tasks so that everyone works on the same number of tasks. However, they cannot assign these tasks evenly. The next day, one team member gets assigned to a different team. The remaining team of three attempts to divide the project tasks again and succeeds! This leads us to wonder: how will we know if we can assign the same number of tasks to each team member? We will answer the question through definitions.

First, we say that _a divides b_ if we can find an integer `k` such that `b = a * k`. If `a` does not divide `b`, then `b/a` leaves a remainder. The operation for finding this remainder is called _modular arithmetic_, and the operator used to perform modular arithmetic is called the _modulus_. We express modulus with `%`, and the script:

```py
print(a % b)
```

outputs the remainder of `a/b`.

Finally, we say that _a is congruent to b mod n_ (where _mod_ is short-hand for modulus) if n divides (a-b); in other words, a is congruent to b mod n if there is an integer `k` such that `a-b = k*n`. In mathematical symbols, we write a is congruent to b mod n as:

```tex
a \equiv b\;(mod\;n)
```

Python can check congruences by verifying that `(a-b) % n = 0`. The script:

```py
# Define a, b, and n such that n > 0
print((a - b) % n == 0)
```

will return `True` if `(a - b) % n = 0` and `False` otherwise.

Note two things: first, `n` is defined to be positive and, second, the remainder `r` is a positive integer such that `0 <= r < n`. Also, `n` cannot be 0 because if `n = 0` then, by definition of congruence, 0 divides `a-b`, which is never true because 0 does not divide any number.

The next exercise will motivate congruences by explaining their relevance to cryptography. After that, we will define three congruence properties, then we will solve simple kinds of congruence problems. For now, however, we will ask you to use Python to check if two integers are congruent to each other mod n.

What Are Congruences?

Good work so far! It turns out that congruences are very much relevant to computer science. If anyone has ever suggested to you that you should encrypt your files using a cipher, then you have indirectly seen congruences in action! One of the earliest and simplest ciphers known in cryptography is the _Caesar cipher_. The cipher takes some user-provided String (or sequences of letters, in this case) and shifts each letter in that String three letters down the alphabet. 

Coding a Caesar cipher in Python requires the knowledge that each letter can be represented by a number. For instance, since A is the first letter in the English alphabet, we cast A as the number 0; likewise, B is set to 1, C is set to 2, and so on until we reach Z, or 25. If we seek to perform a shift in the letter Z, then counting the next letter means returning to the beginning of the alphabet (so starting at A); from there, we continue counting letters until we have counted 3 total. Ultimately, Z will be coded as a C using the Caesar cipher.

Don’t worry, we don't expect you to know how to fully code in this cipher just yet! However, we will ask you in the upcoming checkpoint to perform a Caesar cipher on a simple String by hand and check your result using Python.


Congruences in Cryptography

Now, we will focus on solving _linear congruences_, or congruences with the unknown variable contained within a linear expression. _Linear expressions_ are expressions in the form `ax + b`, where a and b are constants and `x` is our unknown variable. Solving for the unknown variable in a congruence problem is almost identical to solving for `x` in a linear equation: the catch is that each computation in the linear congruence is mod n. In other words, for every operation we perform, we must perform modular arithmetic (% n) on each term except n itself. We will focus on three types of linear congruences. (Note: for all cases, suppose b and c are known positive integers between 1 and n.)

First, suppose we wanted to solve 

```tex
a+c \equiv b\;(mod\;n)
```

for `a` unknown. Subtract c from both sides to obtain:

```tex
a \equiv b-c\;(mod\;n)
```

From here, compute `(b-c) % n`, then solve for a as we did in the previous exercise. If we wanted to solve 

```tex
a-c \equiv b\;(mod\;n) 
```

for `a` unknown, then we would add c to both sides instead.

Now, suppose we wanted to solve 

```tex
ca \equiv b\;(mod\;n)
```

for `a` unknown. Then we can perform modular arithmetic on both c and b mod n (i.e. `c % n` and `b % n`) to reduce the problem to one of three outcomes:

1. Our reduced problem becomes: 0 is congruent to 0 mod n. Since this is always true, any value of a can solve this congruence.
2. Our reduced problem becomes: 0 is congruent to `r` mod n, where `r = b % n` and `0 < r < n`. Since this is never true, the congruence problem has no solutions.
3. Our reduced problem becomes: `sa` is congruent to `r` mod n, where `s = c % n`, `r = b % n`, `0 < s < n`, and `0 <= r < n`. There are infinitely many answers `a` for this problem; the smallest positive solution `a` can be discovered by:

```py
  # Define s, r, and n
  for a in range(0, n):
    if((s * a - r) % n == 0):
      print(a)
      break
```

Lastly, suppose we wanted to solve 

```tex
ca+d \equiv b\;(mod\;n) 
```

for `a` unknown. The procedure for solving for `a` here is a combination of the previous two.


Solving Linear Congruence Problems

Congratulations, we have proved the reflexive property for congruences! The next property of congruences we will verify is another simple idea called the _symmetric property_. The symmetric property for congruences goes like this: if a is congruent to b mod n for integers a, b, and n with n > 0, then b must also be congruent to a mod n. To prove the symmetric property for congruences, we first suppose that a, b, and n are integers with n > 0 such that a is congruent to b mod n. In other words, we know that n divides (a-b), or that
 
```tex
(a - b) = nk
```

for some integer `k`. Multiply both sides by -1:

```tex
-(a - b) = -(nk)
```

Distribute the negative on the left-hand side of the equation and move the negative sign on the right-hand side to obtain:

```tex
-a + b = b - a = -(nk) = n(-k)
```

Since `k` is an integer, its negative (`-k`) is also an integer. We have shown that n divides (b-a), and by the definition of congruence, we have proven that b is congruent to a mod n. Python is quite useful in helping us see the symmetric property in action, and the upcoming checkpoints will ask you to demonstrate this property using code.
