The first problem on the homework was a little interesting. Did you all get the obvious solution?
[(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.
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:
[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 (ab)\, .$$ 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:
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. Tadah!
Sage verifies this is much faster, and even for much bigger powers:
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:
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.
16 <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'> 16 <type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'> 
There are two main sets of propositions that make this possible (Lemmas 3.2 and 3.3 in your text).
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 welldefined 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.
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^{n1}})^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.
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:
