NTIC Powers

Section 8.2 Powers

Let's continue to restrict ourselves to looking at

$\mathbb{Z}_p\text{,}$ the integers modulo some prime

$p\text{,}$ for a bit longer. This will enable us to get a little more detailed in our exploration. We eventually want to explore solutions to congruences modulo primes and prime powers.

🔗

Let's begin by exploring powers. Powers are particularly important, since polynomials are constructed from them. The following interact allows exploration of powers

$a^n$ modulo

$p$ for various primes

$p$ and bases

$a\text{.}$ Notice I have not yet brought in the colors.

xxxxxxxxxx
 
@interact(layout=[['p','a']])
def _(p=(7,prime_range(50)),a=(3,[0..50])):
    b=mod(a,p)
    top=ceil(2*p/10)*10
    pretty_print(html("If we look at some of the powers of $%s$"%(a,)))
    pretty_print(html("modulo the prime $%s$, we get:"%(p,)))
    pretty_print(html("<ul>"))
    for m in [0..top]:
        pretty_print(html(r"<li>$%s^{%s}\equiv %s\text{ (mod }%s)$</li>"%(a,m,b^m,p)))
    pretty_print(html("</ul>"))

🔗

Do you see any patterns? It's probably a little early to try to come up with potential theorems, but there should be at least some patterns you see. Do you maybe even see any theorems we have already proved in here?

🔗

One of the biggest patterns is hard to see in this format, but is the simplest. Given a prime

$p\text{,}$ you should get get the same answers for

$a\equiv a'$ (mod

$p$ ). (Recall this fact was the core of the proof of Fact 6.1.4.) So we should really just restrict ourselves to looking at

$0\leq a\lt p\text{.}$

🔗

Subsection 8.2.1 Returning to visualizing

🔗

Still, this is a lot of data to assimilate. Is there some way to think about it differently?

🔗

This next interact is super-cool, because it combines the short, color-coded format with the much less familiar material of powers.

xxxxxxxxxx
 
import matplotlib.pyplot as plt
from matplotlib.ticker import IndexLocator, FuncFormatter
@interact
def power_table_plot(p=(11,prime_range(100))):
    mycmap = plt.get_cmap('gist_earth',p-1)
    myloc = IndexLocator(floor(p/5),.5)
    myform = FuncFormatter(lambda x,y: int(x+1))
    cbaropts = {  'ticks':myloc, 'drawedges':True, 'boundaries':srange(.5,p+.5,1)}
    P=matrix_plot(matrix(p-1,[mod(a,p)^b for a in range(1,p) for b in srange(p)]), cmap=mycmap,colorbar=True, colorbar_options=cbaropts, ticks=[myloc,myloc], tick_formatter=[None,myform])    
    show(P,figsize=6)

🔗

The default coloring needs some explanation, as they are not the same as in the previous example. The

$a$ row and

$b$ column gives the color corresponding to

$a^b\text{ (mod }p)\text{,}$ where the colors are given by the colorbar on the right. From this we see that the first (

$0$ th) column is all the color for

$a^0=1\text{,}$ and the second (

$1$ th) column gives the colors of each element

$a^1=a$ of

$\mathbb{Z}_p\text{.}$ For instance, since

$3^4\equiv 4$ (mod

$7$ ) in the initial example, it has the color of the color corresponding to

$4\text{.}$

🔗

(As far as I know, this representation first appears in Wagon and Bressoud's excellent computational number theory text [C.4.7]. The PascGalois project has related visualizations.)

🔗

Sage note 8.2.2. Colorful options.

If you don't like the colors, you can change the word in the quotes in the command mycmap = plt.get_cmap(...) (currently 'gist_earth'); for instance, 'gray' gives a grayscale plot, which is most appropriate for certain vision-impaired users. Some others you could try are 'Oranges' or 'hsv' or … Well, see the next Sage cell if you really want to know all of them!

xxxxxxxxxx
 
for c in colormaps:
    print(c)

🔗

What color patterns can you see here? To say it another way, what potential theorems do you see? (Again, do you see any that we already have discussed?)

🔗

In a classroom or self-study situation, I strongly recommend thinking about this until coming up with some nice potential theorem regarding whether there are any patterns in

$a^b$ (mod

$p$ ) that hold for all

$p$ or all

$a$ or all

$b\text{,}$ or something.