# MAT 338 Day 13 2011

## 2825 days ago by kcrisman

Before we get to groups, there is something to remind you of.  Namely, you never did see a pattern with the prime $p$ such that  $$x^2\equiv -1\text{ mod }(p)$$ has a solution!  So let's see this table and see if you can find something.

@interact def _(n=20): yeslist=[] nolist=[] for p in prime_range(3,n): res = 0 for res in [0..p]: if mod(res,p)^2+1 == 0: yeslist.append(p) break else: nolist.append(p) t = [['exist', 'do not exist']] + [[a,b] for (a,b) in map(None,yeslist,nolist)] for item in t: for i in range(len(item)): if item[i] is None: item[i]='' html("Solutions to $x^2\equiv -1$ mod $(p)$ for $2< p <%s$:"%n) html.table(t, header = True)

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

Proving this will be HW!  As will something similar for $x^2+y^2=p$ for such primes $p$.

The reason I point this out is not just because I can, but because it shows simple congruence patterns can have a big result.  Recall our search through Mordell/Bachet curves, and let's look at the particular case $y^2=x^3+7$.

f(x,y)=y^2-x^3-7 @interact def _(viewsize=slider(3,40,1)): p = implicit_plot(f,(x,-viewsize,viewsize),(y,-2*viewsize,2*viewsize),plot_points = 200) lattice_pts = [[i,j] for i in [-viewsize..viewsize] for j in [-2*viewsize..2*viewsize]] plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0),pointsize=2) curve_pts = [coords for coords in lattice_pts if f(coords[0],coords[1])==0] if len(curve_pts)==0: show(p+plot_lattice_pts, figsize = [5,5]) else: plot_curve_pts = points(curve_pts, rgbcolor = (0,0,1),pointsize=20) show(p+plot_lattice_pts+plot_curve_pts, figsize = [5,5]) html("Solutions of $x^3+7=y^2$ in this viewing window")

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

Thus it seems that a perfect square can't ever be exactly seven more than a perfect cube.  Is this true?  Here's where congruences come into play.

What kind of $x$ could solve $y^2=x^3+7$?

• If it's even, then $2|x$, so $8|x^3$.  That means $y^2\equiv 7$ mod $(8)$.
[i^2 for i in Integers(8)]
 [0, 1, 4, 1, 0, 1, 4, 1] [0, 1, 4, 1, 0, 1, 4, 1]

• Unfortunately, the only perfect squares mod 8 seem to be 0, 1, and 4.  Not possible.
• What about if $x$ is odd?  Then $y$ must be even, since $x^3$ and 7 are odd.  So far, plausible.
• So let's examine whether $x\equiv 1$ mod $(4)$ or $x\equiv 3$ mod $(4)$, the next two options.
• If $x\equiv 3$ mod $(4)$, then $x^3\equiv 27\equiv 3$ mod $(4)$, so $x^3+7\equiv 10\equiv 2$ mod $(4)$.
• But we already know from earlier that perfect squares are only $0$ or $1$ modulo $4$, so that's not possible either.
• So it must be the case that $x\equiv 1$ mod $(4)$.  Now we do a trick like that of completing the square: $$y^2=x^3+7\Rightarrow$$ $$y^2+1=x^3+8\Rightarrow$$ $$y^2+1= (x+2)(x^2-2x+4)$$
• If $x\equiv 1$ mod $(4)$, then $x+2\equiv 3$ mod $(4)$.  So not only is $x+2$ an odd number, but also it must be divisible by a prime of the form $4n+3$.  (Otherwise all its primes look like $4n+1\equiv 1$, the product of which would also be $\equiv 1$ mod $(4)$.)
• Thus, this prime not only divides $x+2$, it divides $(x+2)(x^2-2x+4)\ldots$
• And not only does it divide $(x+2)(x^2-2x+4)$, it must then divide $y^2+1$, since they're equal.
• But that's what we just said was not possible!  So this option doesn't work either.

I hope that seems cool enough!  Congruences are amazingly powerful.  So let's make them even more powerful, and bring groups into play.

Next business is to recall what a group is.  In short, a group is any "number system" where we can solve linear equations.

So $\mathbb{Z}_n$ is a group under addition, because $3+x\equiv 2$ mod (4) has a solution.  Namely, we use the (group) inverse, $-3\equiv 1$, to solve it. so that $$x\equiv 2+(-3)\equiv 2+1\equiv 3\text{ mod }(4)$$ is the solution.

Similarly, we can solve equations like $\frac{2}{3}\cdot x=5$ over the rational numbers, because $\frac{2}{3}$ has a (group) inverse in the group $\mathbb{Q}\setminus\{0\}$, $(\frac{2}{3})^{-1}=\frac{3}{2}$, and $$x=5\cdot\frac{3}{2}$$ does indeed solve this equation.

Now we will use this idea to help us with solving congruences modulo $n$.  Using the above framework, I should be able to solve $$43x\equiv 2\text{ mod }(997)$$ by using something like $a=43^{-1}$, the notation we saw before.  That would get us $$x\equiv 2a\equiv 2\cdot 43^{-1}\text{ mod }(997)\; .$$  And below, if I just do the naive thing in Sage, I get the following:

a=mod(43,997) x=2*a^-1 a^-1 html("$a$ is $%s$"%a) html("$a^{-1}$ is $%s$"%a^-1) html("$2a^{-1}$ is $%s$"%x)
 a is 43 a^{-1} is 371 2a^{-1} is 742 a is 43 a^{-1} is 371 2a^{-1} is 742

This checks out, of course:

mod(43*742,997)
 2 2

We can similarly try to solve with a composite modulus: $$53y\equiv 29\text{ mod }(100)$$ using $b=53^{-1}$, so that $$y\equiv 29\cdot b\equiv 29\cdot 53^{-1}\text{ mod }(100)\, .$$

y=29*mod(53,100)^-1 html("$y$ is $%s$"%y)
 y is 93 y is 93
53*y
 29 29

So this should often be possible.  But it can't always work, otherwise I could use it to solve something like $52y\equiv 29$ mod (100), and we already know this does not have a solution.  There isn't a $52^{-1}$ in this case, and so we can't just use this idea willy-nilly.

Hence we introduce a new group - and it's even a simple set to define:

• We let $U_n$, the group of units modulo $n$, be the set of equivalence classes $[a]$ modulo $n$ such that $gcd(a,n)=1$.

This will be the set where we are allowed to do inverses, and hence to solve things easily.

Now, naming something doesn't guarantee it's useful, or that it performs as claimed!  So we need to check some things.

• This is certainly a set.  Since we earlier proved that any two elements of a residue class have the same gcd with a modulus, the definition makes sense, and we know how to check if something is in it.
• This set is associative with respect to multiplication, because it's really the same as multiplication over $\mathbb{Z}$.
• There is an identity element inherited from $\mathbb{Z}$ as well, which is $[1]$, of course.
• Finally, the multiplication is closed on this set.  After all, it's not obvious that if $ax\equiv 1$ and $bx\equiv 1$ have solutions, then so does $(ab)x\equiv 1$!  But it does work.
• First, $b^{-1}$ and $a^{-1}$ exist, so $(b^{-1})(a^{-1})$ exists.
• Next, $$(b^{-1}a^{-1})(ab)x\equiv (b^{-1}a^{-1})\cdot 1$$
• So $$(b^{-1}\cdot 1\cdot b)x\equiv b^{-1}a^{-1}\text{, which is }x\equiv b^{-1}a^{-1}$$
• So $ab$ has an inverse as well, and $U_n$ really and truly is a group.

The terminology units makes sense too.  If you are in a number system with addition and multiplication, then a unit is an element that has a multiplicative inverse.

In the integers, $\pm 1$ are the units.  More unusual is the set of complex numbers (!), which all are units except 0. (In fact, the inverse of $r\left(\cos(\theta)+i\sin(\theta)\right)$ is $\frac{1}{r}\left(\cos(-\theta)+i\sin(-\theta)\right)$.).

So $U_n$ is the set of all the integers modulo $n$ that have multiplicative inverses.  By our previous investigations, we know this is when $ax\equiv 1$ mod ($n$) has a solution.  Since multiplication is the operation, there are inverses!

Naturally, it can take a while to list all these guys.  Try it for $n=10$, $n=11$, and $n=12$ by hand.

It turns out that Sage has commands to list the group of units and give the order of the group.

@interact def _(n=14): html("The units of $\\mathbb{Z}_{%s}$ are"%n) html(Integers(n).list_of_elements_of_multiplicative_group()) html("There are $%s$ of them."%Integers(n).unit_group_order())

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

You can use these yourself by doing the commands below as well, though they are a little long to type out!  (There is a new command for going straight to them in the works, but it gives away some of our investigation, so I am choosing not to use it.)

Integers(50).list_of_elements_of_multiplicative_group()
 [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49] [1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49]
Integers(50).unit_group_order()
 20 20

We give the size of the group of units mod ($n$) a special name.

• We call the order of $U_n$ by the name $\phi(n)$.  That is, by definition, $$\phi(n)=|U_n |\; .$$

This is the so-called Euler $\phi$ function.  It can also be written phi, it is pronounced 'fee', and it's occasionally notated $\varphi$ just for fun.  Do you see any patterns on the value of $\phi(n)$?   Let's take some time to inspect this.

Now, so far this is a relatively abstract concept.  What follows is not abstract at all, but very, very useful!

• Suppose you take some random element $[a]\in U_n$, for some $n$.
• Like any other element of a group, it has an order.  For instance, the order of $[2]$ in $U_7$ is 3, because $[2]^1$ and $[2]^2$ are not $1$, but $[2]^3\equiv 8\equiv 1$ mod (7).  So all the stuff we learned about groups and their orders last time still applies, and thankfully, it is now written multiplicatively like our theorems!
• In particular, we can apply the theorem of Lagrange (the group theory one) from last time.  It stated that the order of any element of a finite group divides the order of the group itself.  So $|a|$ divides $|U_n|$.  For instance, in the example above, 3 divides 6.
• So we can say that $|a|$ divides $\phi(n)$, or $\phi(n)=k|a|$ for some positive integer $k$.
• Let's now apply this to $a$.  (Notice that $a^{|a|}\equiv 1$ because that's the definition of what 'order' means!) $$a^{\phi(n)}=a^{k|a|}=(a^{|a|})^k\equiv 1^k\equiv 1\text{ mod }(n)$$

Thus Lagrange's Theorem nearly immediately gives us one of Euler's many celebrated Theorems:

Euler's Theorem: If $gcd(a,n)=1$, then $a^{\phi(n)}\equiv 1$ mod ($n$).

If you guessed well on patterns in $\phi(n)$, you should see how to recover Fermat's Little Theorem from this.

We can use this to compute, too.  One has to be just a little clever to use it to compute inverses mod $(n)$. If $$a^{\phi(n)}\equiv 1\text{ mod }(n)\; ,$$ then certainly multiplying both sides by $a^{-1}$ yields $$a^{\phi(n)-1}\equiv a^{-1}\text{ mod }(n)\; .$$  We can check this using Sage.

@interact def _(a=3,n=10): a=mod(a,n) try: b = a^-1 html("$%s^{-1}$ is $%s$ and $%s^{\phi(%s)-1}=%s^{%s-1}$ is also $%s$"%(a,b,a,n,a,euler_phi(n),a^(euler_phi(n)-1))) except: html("Don't forget to pick an $a$ that actually has an inverse modulo $n$!")

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

So to solve things like $$53y\equiv 29\text{ mod }(100)$$ from earlier, we could in theory multiply both sides by the inverse of 53 in this form, or $$y\equiv 29\cdot 53^{\phi(100)-1}\text{ mod }(100)\; .$$  This would look like the following in Sage.

mod(29*53^(euler_phi(100)-1),100)
 93 93

This answer jells with our previous calculation.  And now I didn't have to solve a different linear congruence in order to solve my original one; I just have to have a way to do multiplication mod $(n)$.

Notice that Sage has a command to get $\phi(n)$, namely $\verb+euler_phi(n)+$.  This is much easier to use, but doesn't have the direct connection that $\verb+Integers(n).unit_group_order()+$ does, of course.

Our final use of this for today is again computational.  Namely, it turns out that we can use this to do Chinese Remainder Theorem systems much more easily, as long as we have access to $\phi$.

Remember that in the algorithm for the CRT, where we tried to solve systems like

• $x\equiv a_1$ mod ($n_1$)
• $x\equiv a_2$ mod ($n_2$)
• $\cdots$

There, we had to calculate many solutions to congruences of the form $$\frac{N}{n_i}x\equiv 1\text{ mod }(n_i)\; .$$  (This was to get the $d_i$ numbers.) Our new information means that this inverse is just $$\left(\frac{N}{n_i}\right)^{-1}\equiv \left(\frac{N}{n_i}\right)^{\phi(n_i)-1}\; ,$$ since we are looking at a congruence modulo $n_i$.   So the things in the final solution which looked like $$a_i\cdot \frac{N}{n_i}\cdot \left(\frac{N}{n_i}\right)^{-1}$$ can be thought of as $$a_i\cdot \frac{N}{n_i}\cdot \left(\frac{N}{n_i}\right)^{\phi(n_i)-1}=a_i\left(\frac{N}{n_i}\right)^{\phi(n_i)}\; ,$$ which is much cooler and simpler!  So the answer to the general system is just $$x\equiv \sum_{i=1}^k a_i \Big(\frac{N}{n_i}\Big)^{\phi(n_i)}\, .$$

a_1,a_2,a_3 = 1,2,3 n_1,n_2,n_3 = 5,6,7 N=n_1*n_2*n_3;N
 210 210
mod(a_1*(N/n_1)^(euler_phi(n_1))+a_2*(N/n_2)^(euler_phi(n_2))+a_3*(N/n_3)^(euler_phi(n_3)),N)
 206 206

It's possible to do it more concisely if you know a little Python and something called 'list comprehension'.

sum([mod(a*(N/n)^(euler_phi(n)),N) for (a,n) in [(a_1,n_1),(a_2,n_2),(a_3,n_3)]])
 206 206

But that's not necessary for our purposes.

We can do this one step even better.  Take a huge system like

• $3x\equiv 7$ mod (10)
• $2x\equiv 5$ mod (9)
• $4x\equiv 1$ mod (7)

Can we find solutions for this using the same mechanism?  Yes, and without too much difficulty now.

Since one can solve $bx\equiv c$ mod ($n$) with $$x\equiv b^{\phi(n)-1}\cdot c\; ,$$ any likely system of congruences with coprime moduli $$b_i x\equiv c_i\text{ mod }(n_i)$$ where $N$ is the product of the moduli could be solved by $$x\equiv \sum_{i=1}^k \left(b_i^{\phi(n_i)-1}c_i\right)\left(\frac{N}{n_i}\right)^{\phi(n_i)}\text{ mod }(N)\, .$$  Let's use this to solve the system above,

• $3x\equiv 7$ mod (10)
• $2x\equiv 5$ mod (9)
• $4x\equiv 1$ mod (7)
c_1,c_2,c_3 = 7,5,1 m_1,m_2,m_3 = 10,9,7 M=m_1*m_2*m_3 b_1,b_2,b_3 = mod(3,M),mod(2,M),mod(4,M) d_1,d_2,d_3 = mod(M/m_1,M),mod(M/m_2,M),mod(M/m_3,M) b_1^(euler_phi(m_1)-1)*c_1*d_1^(euler_phi(m_1))+b_2^(euler_phi(m_2)-1)*c_2*d_2^(euler_phi(m_2))+b_3^(euler_phi(m_3)-1)*c_3*d_3^(euler_phi(m_3))
 79 79

Notice that we make as much stuff modulo $M$ to begin with as possible.  Even for bigger numbers, asking Sage to first make things modular is a big help - it takes essentially no time! We can demonstrate this with a much larger example, picking essentially random large primes to compute with.

%time c_1,c_2,c_3 = 7,5,1 m_1,m_2,m_3 = random_prime(10000),random_prime(20000),random_prime(30000) M=m_1*m_2*m_3 b_1,b_2,b_3 = mod(3,M),mod(2,M),mod(4,M) d_1,d_2,d_3 = mod(M/m_1,M),mod(M/m_2,M),mod(M/m_3,M) html("Our primes are $%s$, $%s$, and $%s$"%(m_1,m_2,m_3)) b_1^(euler_phi(m_1)-1)*c_1*d_1^(euler_phi(m_1))+b_2^(euler_phi(m_2)-1)*c_2*d_2^(euler_phi(m_2))+b_3^(euler_phi(m_3)-1)*c_3*d_3^(euler_phi(m_3))
 Our primes are 2753, 577, and 6427 6752297785 CPU time: 0.01 s, Wall time: 0.01 s Our primes are 2753, 577, and 6427 6752297785 CPU time: 0.01 s, Wall time: 0.01 s
%time c_1,c_2,c_3 = 7,5,1 m_1,m_2,m_3 = random_prime(10^8),random_prime(2*10^8),random_prime(3*10^8) M=m_1*m_2*m_3 b_1,b_2,b_3 = mod(3,M),mod(2,M),mod(4,M) d_1,d_2,d_3 = mod(M/m_1,M),mod(M/m_2,M),mod(M/m_3,M) html("Our primes are $%s$, $%s$, and $%s$"%(m_1,m_2,m_3)) b_1^(euler_phi(m_1)-1)*c_1*d_1^(euler_phi(m_1))+b_2^(euler_phi(m_2)-1)*c_2*d_2^(euler_phi(m_2))+b_3^(euler_phi(m_3)-1)*c_3*d_3^(euler_phi(m_3))
 Our primes are 29019637, 19020247, and 180032459 57792586318644815467045 CPU time: 0.01 s, Wall time: 0.01 s Our primes are 29019637, 19020247, and 180032459 57792586318644815467045 CPU time: 0.01 s, Wall time: 0.01 s

Homework for Monday - not handed in, but many likely to reappear for handing in Wednesday!

1. Prove that it is impossible for $p|x^2+1$ if $p\equiv 3$ mod ($4$) - that is, if $p$ is of the form $4n+3$.  (Hint: look at everything modulo 4.)
2. Prove that $x^2+y^2=p$ has no (integer) solutions for $p$ with that same form.
3. Show that $y^2=x^3+999$ has no (integer) solutions.
4. Prove Fermat's Little Theorem as a corollary of Euler's Theorem.
5. Prove that if $p$ is prime, then $a^p\equiv a$ mod ($p$) for every integer $a$.
6. Formally prove that $\phi(p)=p-1$ for prime $p$, by deciding which $[a]\in \{[0],[1],[2],\ldots,[p-2],[p-1]\}$ have $gcd(a,p)=1$.
7. Verify Euler's Theorem by hand (shouldn't even need calculator?) for $n=15$ (note that $\phi(15)=8$, and remember that $a^8=((a^2)^2)^2$ so we can use modulo reduction at each squaring).
8. Get the inverse of 29 modulo 31, 33, and 34 using Euler's Theorem.
9. Evaluate without a calculator $12^{49}$ mod (15) and $139^{112}$ mod (27).
10. Solve as many of the simple linear congruences we already did (such as those in Chapter 3.2, in notes, on homework) using Euler's Theorem as you need to in order to understand how it works.  Follow the models above closely if necessary.
11. Solve as many of the systems of congruences we already did (such as those in Chapter 3.3, in notes, on homework) using the CRT and Euler's Theorem as you need in order to understand how it works.  Follow the models above closely if necessary.