# MAT 338 Day 7 2011

## 2483 days ago by kcrisman

Let's first review from last time the concept of doing arithmetic modulo $n$ - which at the very end of last time we called arithmetic in the set $\mathbb{Z}_n$.

• Remember, we should first reduce modulo $n$, then do our arithmetic (add, multiply, exponentiate); we proved last time that those things are well-defined.
• Notice that with exponentiation you can only replace the base with something in the same congruence class.  Do on your own the comparison between $$2^3\text{ mod }(5), \; 7^3 \text{ mod }(5),\; \text{ and }2^8 \text{ mod }(5)\; .$$ Hence although we can assume $[a]^n$ is well-defined, there is no guarantee that $a^{[n]}$ makes any sense.
• We should also use whichever residue of a number modulo $n$ is convenient for our purposes.  For instance, if we are trying to add $22$ and $21$ modulo $23$ (which we call $[22]+[21]$), we might want to use the residues $-1\in[22]$ and $-2\in [21]$ to do that, since there is less arithmetic to do.  We'd get $[-3]$ as the answer, which is of course the same as $[22+21]=[43]=[20]$ modulo $23$.
mod(22,23)+mod(21,23)
 20 20

We can check if two numerical expressions are equal using '=='.

mod(22,23)+mod(21,23)==mod(-3,23)
 True True

What we will now embark upon is asking all the same questions (and many more) about the integers modulo $n$ that we asked about the integers themselves.  So we will focus on congruences, which are simply equations modulo $n$.  For example, one could ask for solutions to any of these ideas:

• $2x+3y=5$ (solutions would be pairs of integers)
• $2x+3y\equiv 5\text{ mod }(7)$ (solutions would be pairs of equivalence classes $[x],[y]$ modulo 7)
• $2x+3y\equiv 5\text{ mod }(n)$ for any particular $n$ (solutions would be triplets $[x],[y],n$, since it would depend on $n$)

This may not seem better, but actually it's a big improvement - after all, you just have to try $x,y$ from 0 to 6 (the least nonnegative residues) in the congruence $2x+3y\equiv 5$ mod (7).  Or, as we say it, we are looking for all solutions in the mathematical structure $\mathbb{Z}_{7}$.

The homework question about possible last digits of a perfect cube can be thought of in this way.  After all, if the last digit of $x$ is 3, then $x=10m+3$ for some integer $m$ (assuming $x$ is positive, anyway), and so $[x]=[3]$ modulo (10).    Here is how we can ask Sage to do it very quickly:

[mod(i,10)^3 for i in [0..9]]
 [0, 1, 8, 7, 4, 5, 6, 3, 2, 9] [0, 1, 8, 7, 4, 5, 6, 3, 2, 9]

If you check, what this is doing is the residue modulo 10 of every possible last digit (0 to 9, which Sage does [0..9]).  And since we just said the last digit is all that matters, it turns out that thus there is a solution modulo 10 to $$x^3\equiv d\text{ mod }(10)$$ for all ten last digits $d$.

Incidentally, that means every number in $\mathbb{Z}_{10}$ has a cube root.   For instance, the cube root of $[7]$ is $[3]$.  This is definitely not true in $\mathbb{Z}$ for a cube root of 7 (not $[7]$), which would be irrational even!

[mod(i,4)^3 for i in [0..3]]
 [0, 1, 0, 3] [0, 1, 0, 3]

So it looks like every element of $\mathbb{Z}_4$ has a cube root except $[2]$.

Here's another question we can ask.  Over the integers, there are only two solutions to $x^2=x$ - namely, $x=0$ and $x=1$.  What about solutions to the congruence $x^2\equiv x$ mod ($n$) for different moduli $n$?  We'll do this with the following command, which is very naive.

@interact def _(n=(2,[0..100])): list=[x for x in [0..n-1] if (mod(x,n)==mod(x,n)^2)] html("The solutions to the congruence $x^2\equiv x$ mod ($%s$)"%(n,)) html("are "+str(list))

## Click to the left again to hide and once more to show the dynamic interactive window

Often, it seems we get the same answers.  But not always!  Can you try to conjecture when we do get the same answer?

Here is an example of another homework proof, just to give you the idea.

Let's try to prove that if $a^3 \mid b^2$, then $a\mid b$.  By the Fundamental Theorem of Arithmetic, we know that $a$ and $b$ may both be written as a product of prime powers $p_i^{e_i}$ or $q_j^{f_j}$.  If $a^3\mid b^2$, then for each $i$, $(p_i^{e_i})^3 \mid b^2$, so $p_i \mid b^2$, so in fact by the FTA $p_i$ is one of the $q_j$.  So that will simplify our notation a bit.

Now, it is specifically true for each of the $p_i$ that $p_i^{3e_i}\mid b^2$, and the only part it can divide is the $p_i$ part.  We can write this as $$p_i^{3e_i}\mid p_i^{2f_i}\, .$$ But that is the same as saying that $3e_i\leq 2f_i$, or $e_i\leq \frac{2}{3}f_i$.  However, $\frac{2}{3}f_i<f_i$, so in fact $e_i<f_i$, which means that all powers of $a$ will be less than all powers of $b$.  Hooray!

In fact, it proves more; it proves that if $a^3\mid b^2$, then $a < b$ by a rather sizeable amount, as every prime power in $a$ must be at most two-thirds of the exponent in $b$.  That's called milking the proof for more information.

To business.  Our goal for today is to completely solve all linear congruences $ax\equiv b$ mod ($n$).  In order to do that, we will use several facts.

• The most important one is that we know exactly when there is a solution: $ax\equiv b$ mod ($n$) has a solution precisely when $gcd(a,n)\mid b$.  (This theorem also gives us all possible solutions, if we have one specific solution.)

Let's take a look at the proof of this (Theorem 3.7).  All we do is reduce to the linear Diophantine equations we completely understand.  So we morph $$ax\equiv b\text{ mod }(n)$$ to $$n|ax-b$$ to $$ax-b=ny\Rightarrow ax-ny=b\; !$$  And we already know how to solve this.  We don't care about $y$ (other than that it exists), so the solutions are $x_0+\frac{n}{d}t$ for integer $t$, where $d=gcd(a,n)$.

Note also that it gives us the exact number of solutions, because letting $t$ go from 0 to $d-1$ will give all different solutions.  (Also note the parenthetical comment just after the statement of the theorem in the book - everything is one congruence class, modulo $\frac{n}{d}$.)

Let's try this with Exercise 3.5 - solving $$12x\equiv 9\text{ mod }(15)\; .$$  Here, $gcd(a,n)=3$, so we will  have 3 solutions, all congruent mod ($\frac{n}{d}=\frac{15}{3}=5$).   Trying small values gives us $12(1)=12\not\equiv 9$, but $12(2)=24\equiv 9$ mod (15)!  So $x=2$ is our $x_0$, and then since all other solutions are equivalent mod (5), we can see that $x=[2],[7],[-3]$ all work - or, as the book often puts it, $2+5t,\, t\in\mathbb{Z}$ is the general solution.

This always works. However, it can be tedious to find that first solution!  That is the reason the book has such a long strategy.  Don't be confused by the heavy notation and proliferation of primes; we'll get a chance to look at all of it in a second.  First, let me prove one of the secondary facts we will use.

Proposition: If $a\neq 0$, then $ab\equiv ac$ mod ($an$) precisely for the same $b,c,n$ as when $b\equiv c$ mod ($n$).

Proof: We write $ab\equiv ac$ mod ($an$) as $ab-ac\mid an$, or $ab-ac=k(an)$ for some $k\in\mathbb{Z}$; all of this is by definition.  We rewrite this as $a(b-c)=a(kn)$.  Since $a\neq 0$, $$a(b-c)=a(kn)\text{ is equivalent to saying }b-c=kn\, ,$$ which is of course by definition saying that $b\equiv c$ mod ($n$).  Since all steps were equivalences, both statements are equivalent.

So there are some things we can do to find that first solution.  These seem straightforward.

• We can cancel all the (nonzero) $a$s from any modular equation $ab\equiv ac$ mod ($an$), to get $b\equiv c$ mod ($n$).  (We just proved this.)
• We can cancel the $a$s from a modular equation $ab\equiv ac$ mod ($n$) if $gcd(a,n)=1$.  (This is easy too.  Try it now, using the property of relatively prime when dividing a product.)
• There are also some more tricky things we can do, if they help.

• We can multiply $bx\equiv c$ mod ($n$) by some number $a$ which is coprime to $n$, if it happens to make the coefficients smaller!
• We can add some multiple of $n$ to $c$, if it happens to make $b$ and $c$ share a factor!
• So let's do a big problem exemplifying all the steps.

$$\text{ Solve }30x\equiv 18{ mod }(33)\; .$$

1. First, note that all three are divisible by $3$.  So right away we should simplify by dividing by 3 - keeping in mind that our final solution will need to be modulo 33, not modulo 11!  We should end up with $gcd(30,33)=3$ total solutions.
2. Now we have $10x\equiv 6$ mod (11).  (Again, although this will have one solution modulo 11, we will need to get the other two solutions modulo 33.)  Since 10 and 6 are both divisible by 2, and since $gcd(2,11)=1$, we can divide out by $2$ without any other muss.
3. Having arrived at $5x\equiv 3$ mod (11), I could begin trial and error.  But since $x=1$ and $x=2$ don't immediately work, and because I don't want to try all eight other possibilities, I will try the trick.  I will replace 3 by another number congruent to 3 modulo 11!  Then maybe I can reduce some more.  Although $3+11=14$ doesn't share a divisor with $5$ (from the $5x$), $3+22=25$ does share a divisor with $5$, so I try that replacement.
4. Our next equation, $5x\equiv 25$ mod (11), now reduces to $x\equiv 5$ mod (11).  And that's the answer!  Or is it?
5. Finally, I need to remember that I started modulo 33, and that all my answers will be equivalent modulo 11.  So I see that $x=5+11t$ for $t\in\mathbb{Z}$ will be the answer, which is $\{[5],[16],[27]\}$.  I check this out:

[mod(30*x,33)==18 for x in [5,16,27]]
 [True, True, True] [True, True, True]

Of course, it would be most convenient to use the other trick to multiply $a$ by something which would reduce to $[a]\equiv [1]$.  Let's try that, for comparison.

We were at $5x\equiv 3$ mod (11); multiplying by $9$, which is coprime to $11$, gives us $$45x\equiv 27\text{ mod }(11)$$ which reduces to $x\equiv 5$, and gives the same answer as before.

Even though the book obscures it, this is the algorithm.  Try one of Exercise 3.7 on your own now.

Finally, some homework for Monday.

1. Find some $a$ and $n$ such that $a^n$ mod (6) equals $a^{n+6}$ mod (6), where $a\not\equiv 0,1$ and $n\neq 0,1$.  Then try to find an example where they are not equal.
2. Prove that the only solutions of $x^2\equiv x$ mod ($p$) are $x=[0]$ and $x=[1]$, if $p$ is a prime.
3. Try to decide for exactly which composite moduli $n$ the previous question is true.  Experiment!
4. We know (for instance, from Lemma 3.3) that $b\equiv c$ mod ($n$) implies $ab\equiv ac$ mod ($n$) as well.  Prove that the converse is true if $gcd(a,n)=1$, and give a counterexample where the converse fails if $gcd(a,n)\neq 1$.
5. Find all solutions to the following linear congruences:
• $18x\equiv 42$ mod (50) (This is from Exercise 3.7, but show your work.)
• $15x\equiv 9$ mod (25)
• $6x\equiv 3$ mod (9)
• $980x\equiv 1540$ mod (1600)

 1 1