# MAT 338 Day 6 2011

## 2483 days ago by kcrisman

The first problem on the homework was a little interesting.  Did you all get the obvious solution?

end_range=10 [(n,m) for n in range(1,end_range) for m in range(n+1,end_range) if n^m==m^n]
 [(2, 4)] [(2, 4)]

It's fun to redo some of these theorems with the FTA.  For instance, it becomes apparent why $lcm(a,b)gcd(a,b)=ab$; for each prime $p$ in the factorization of $a$ and/or $b$, the bigger power of $p$ must be the power in the least common multiple (since you need a multiple), and the smaller power of $p$ must be the power in the greatest common divisor (since you need it to divide both $a$ and $b$).  So for each $p$, the statement turns into $$p^{e}p^{f}=p^{max(e,f)}p^{min(e,f)}\; ,$$ which is obvious.

Our goal for the next two weeks (up to the midterm) is to talk about a better notion of how to deal with divisibility and remainders, one we are all familiar with.  That is the notion of congruences

Today will mostly be to review that notion, and start asking the kinds of questions that one will be able to ask with this notion.  Let's start by a little calculation.

mod(25,6)
 1 1

In general, the command $mod(x,m)$ computes $x$ modulo $m$, which is to say the remainder of $x$ when you divide by $m$.  Pretty straightforward.

Because of the division algorithm, we know that there is a unique such remainder, i.e. $0\leq mod(x,m)<m$, which is very important.  But of course lots and lots of different numbers can have the same remainder:

[mod(x,6) for x in [1, 7, 13, 19, 25, -5, -11, 6001, -17]]
 [1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1]

So in mathematics, what we often do is connect all such $x$ with a relation.  A relation is a very vague notion, and basically it exists once you define it.  Our relation will be called congruence, and it is massively important.  It is also relatively new!  We essentially use the same definitions and notation that Gauss came up with just two centuries ago: $$\text{We say that }a\text{ is congruent to }b\text{ modulo }n\text{, or }a \equiv b \text{ mod }(n)\text{, precisely if }n\mid (a-b)\, .$$  It is easy to see (e.g., Lemma 3.1) that this is exactly the same thing as leaving the same remainder.  In our case, it becomes clear that $25\equiv 1\equiv -5$ mod ($n$).

It's fun to use congruence as a conceptual assistant.  For instance, we can try to recast the fact about remainders when dividing by four as saying that $x^2\equiv 0\text{ or }1$ mod (4), and nothing else is possible.  Try to use this idea to think of possible last digits of a square - what modulus would you use?  What about cubes - what remainders are possible modulo 4?  What last digits are possible?

Okay, that's all fun.  But we need power, too.  And that power is what makes calculating $2^{1000000000}$ mod (3) instantaneous for me - it's 1!  I check it with Sage:

time mod(2^1000000000,3)
 1 Time: CPU 0.40 s, Wall: 0.86 s 1 Time: CPU 0.40 s, Wall: 0.86 s

Hmm, but that took more than a few milliseconds.  (In fact, if I add one more zero, it will throw an error.)  Yet I did it instantaneously in my head.   Of course, the reason is not that I am clever, but that congruence can be turned into arithmetic!

For instance, it turns out that if $a\equiv b$ mod ($n$), then $a^m\equiv b^m$ mod ($n$), no matter how huge $m$ is!  Now I reveal my secret: $2\equiv -1$ mod (3), and $-1^{1000000000}=1$, like all even powers of negative one.  Ta-dah!

Sage verifies this is much faster, and even for much bigger powers:

mod(2,3)^1000000000; mod(2,3)^1000000000000000000000000000030
 1 1 1 1

Of course, this can get annoying.  So instead we can assign our 'modulo integer' a name, like $b$, and then just do as normal.  This makes it easy to do lots of interesting tests:

b=mod(2000,31) b;b^1000;b^2000;b^3000;b^4000
 16 1 1 1 1 16 1 1 1 1

Notice that I'm not tricking you here; I definitely couldn't do this one in my head.  The next cell tells you what $b$ really is, as well as confirms that Sage is using modular numbers, not normal integers.

b;type(b)
 16  16 

There are two main sets of propositions that make this possible (Lemmas 3.2 and 3.3 in your text).

1. Congruence is reflexive, symmetric, and transitive.  That is, all the things you know are true about equality are also true about congruence (with a particular modulus $n$ picked, of course).  For instance, $2\equiv 3$ mod ($n$) is the same thing as saying $3\equiv 2$ mod ($n$).
2. Congruence is well-defined with respect to addition and multiplication.  (Those who were in MAT 231, now you know why we spent so much time on this.)  That is, if $a\equiv c$ and $b\equiv d$ (modulo some fixed $n$), then $a+b\equiv c+d$ and $ab\equiv cd$.  The proofs are not hard.

That means I can substitute any number congruent to $a$ for a calculation with $a$; above, I substituted $-1$ for $2$, because they are congruent to each other modulo $3$.   I call a number congruent to $a$ a residue of $a$, and I call the collection of all residues of $a$ the equivalence class of $a$, with notation $[a]=\{\text{all numbers congruent to }a\text{ modulo }n\}$.

So, for instance, the equivalence class we started with is $[1]=\{1, 7, 13, 19, 25, -5, -11, 6001,\ldots\}$, perhaps better written as $\{1+6n\mid n\in\mathbb{Z}\}=[1]$.  You can choose your favorite number in an equivalence class to serve as a representative for all of them.  Note that for the congruence relation, there are of course only finitely many classes, otherwise the division algorithm would be meaningless.  The whole idea is that there are only $n$ possible remainders!

Now, not to worry, I could have done it another way.  Namely: $$2^{1000000000}=(2^2)^{500000000}= 4^{500000000}\equiv 1^{500000000}=1\, .$$  What would not have been legal is first reducing $1000000000$ modulo $3$, which is to 1, because $2^1\not\equiv 1$ mod ($3$)!

See pages 40 and 41 of your text for more details on this.  For instance, proving addition is well-defined goes like this: there must exist $k$ and $l$ such that $a=c+kn$ and $b=d+ln$, so $a+b=c+kn+d+ln=(c+d)+(k+l)n$, which means they have the same remainder modulo $n$.

As you saw above, knowing the 'right' residue can be very helpful.  Because of this, we make two sets of them for general use; we call them complete residue system or complete set of residues for a given modulus.

• Usually, we just use the 'normal' remainders; this is called the set of least nonnegative residues.  This is just what you think it is; for $n=6$, it is $\{0,1,2,3,4,5\}$, representing the set of equivalence classes $\{[0],[1],[2],[3],[4],[5]\}$.  They are easy to think of and understand.
• But, the problem is that they get big!  To calculate $4^{20}$ mod ($6$), I need to reduce a lot, e.g. $$4^{20}\equiv (4^2)^{10}\equiv 16^{10}\equiv 4^{10}\equiv (4^2)^5\equiv 16^5\equiv 4^5\equiv (4^2)^2\cdot 4\equiv 4^2\cdot 4\equiv 4\cdot 4\equiv 4\, ;$$ it's at least a little easier on the ol' noggin (since $4\equiv -2$ mod ($6$)), to do $$4^{20}\equiv (-2)^{20}\equiv ((-2)^2)^{10}\equiv 4^{10}\equiv (-2)^{10}\equiv ((-2)^2)^5\equiv 4^5\equiv (-2)^5\equiv ((-2)^2)^2\cdot (-2)\equiv 4^2\cdot (-2)\equiv (-2)^3\equiv -8\equiv 4\, .$$  Notice in the second one I never broke single digits!  So we sometimes use the set of least absolute residues, in this case $\{-2,-1,0,1,2,3\}$ for $\{[4],[5],[0],[1],[2],[3]\}$.

It turns out that there is a way to make an algorithm out of this.  We take advantage of the fact that for any number $a$, $a^{2^1}=a^2$, $a^{2^2}=(a^2)^2$, $a^{2^3}=(a^{2^2})^2$, and in general $a^{2^n}=(a^{2^{n-1}})^2$.

For instance, to compute $x^{20}$, compute $x^2$, square that for $(x^2)^2=x^{2^2}$, and square twice more for $x^{2^3}$ and $x^{2^4}$ - reducing modulo $n$ at each point.  Now write $$x^{20}=x^{2^4+2^2}=x^{2^2}\cdot x^{2^4}$$ and do this final multiplication mod ($n$)!  You might want to try it to see you get the same thing.

I can try that with something more annoying - calculating $2^{23}$ mod ($11$): $$23=2^4+2^2+2+1\text{, so }2^{23}=2^{2^4}\cdot 2^{2^2}\cdot 2^2\cdot 2\, .\text{ Now }2^2\equiv 4\text{ mod (11), }4^2\equiv 5\text{ mod (11), }5^2\equiv 3\text{ mod (11), and }3^2\equiv 9\text{ mod (11),}$$ $$\text{so we get }2^{2^4}\cdot 2^{2^2}\cdot 2^2\cdot 2\equiv 9\cdot 5\cdot 4\cdot 2\equiv 18\cdot 20\equiv 7\cdot 9\equiv 63\equiv -3\equiv 8\text{ mod (11) --all by hand!}$$

(Those interested in efficiency should note that this requires roughly two times the number of binary digits of your number operations, or about $2\log_2 (n)$ operations, as opposed to normal powers which might require $n$ operations; in addition, you only deal with numbers at most size $n^2$, as opposed to gigantic ones, when you mod out after each step.)

This has been fun and all.  But why are we doing all this?  There are two reasons.

• Practical: It makes it much easier to solve certain otherwise very difficult problems about integers, because we can check whether things are possible when we look at things just modulo $n$.
• We won't talk about this as much today, but Example 3.7 is a perfect illustration of this kind of thing.
• I should point out that we can also prove (some) things like 'The curve $x^3=y^2-7$ has no lattice points' with congruences quite easily.
• Theoretical: We get a new number system - which has new problems, new solutions, and new things to explore!

Definition: We call the set of equivalence classes modulo $n$ the integers modulo n, and denote them by $\mathbb{Z}_n$.

Homework to hand in:

1. Prove that 360 cannot be the area of a primitive Pythagorean triple triangle.
2. Prove that in a primitive Pythagorean triple $x,y,z$, if $y$ is the even one, it is divisible by 4, and that exactly one of $x,y$ are divisible by 3.
3. Find three prime repunits.
4. Prove using the FTA that if $gcd(a,b)=d$ then $gcd\left(\frac{a}{d},\frac{b}{d}\right)=1$.
5. Show that if $a$ and $b$ are positive integers such that $a^3|b^2$, then $a|b$.
6. Show that $\log_{10}(5)$ is irrational.  (Hint; last digits.)
7. By hand, find the prime factorization of $36$, $756$, and $1001$, and their pairwise gcd and lcm.
8. Find and prove the possible last digits for a perfect square and perfect cube.
9. Prove that if the sum of digits of a number is divisible by 3, then so is the number.  Hint: Write 225 as $2\cdot10^2+2\cdot 10+5$.  Can you prove the same thing for 9?
10. Give the least absolute residues and the least nonnegative residues for $n=21$.
11. Prove that 13 divides $145^6+1$ and 431 divides $2^{43}-1$ without a computer (but definitely using congruences).
12. Compute $7^{43}$ mod ($11$) the way I did in class (using powers of 2), without using Sage or anything that can actually do modular arithmetic.  You should never have to compute a number bigger than $(11-1)^2=100$, so it shouldn't be too traumatic.)
13. For which positive integers $m$ is $27\equiv 5$ mod ($m$)?
14. Prove that $m^n=n^m$ is only valid if $n=m$ or the one example you got, by following these steps:
• Assume $m>n$.
• Write $m$ and $n$ as products of powers of primes as in the FTA.
• Show that $m$ and $n$ must have the same actual primes as divisors.
• Show that $m>n$ implies that $m$ also always has a greater power of any prime divisor $p$.
• Show this implies $m$ is divisible by $n$.
• Use this to get an equation which has as its only solutions the situation where $m=n$ or the other one you already got.