Modular arithmetic has a lot of weird properties we don't find in conventional arithmetic. The idea that you can get any number mod 23 by raising powers of 5 is pretty strange, but it's true.
Let's first review what we mean by "primitive roots of 23". A primitive root modulo n is a number g such that every number a coprime to n is equal to some power of g, mod n; that is,
`forall a exists k : g^k equiv a mod n`
The value of k, the power you have to raise to, is the index.
Since 23 is prime, this is really all a (other than 0), whereas for a composite base (such as mod 8 or mod 10) we'd have to exclude factors of the base.
So what we're looking for is the numbers g that satisfy this, as well as the values of k that make it work.
I think the simplest way to start is just to write out a table of values and their powers, mod 23. (I think this is what your teacher means by an "index table", though that can also mean a couple of other things.) Most of the powers will eventually end up with an infinite series of 1s at the end.
A few of them will have every single number somewhere in their list; those are the primitive roots of 23.
original value | powers
0 | 0, 0, 0, ...
1 | 1, 1, 1, ...
2 | 2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1, 1, 1, ...
3 | 3, 9, 4, 12, 13, 16, 2, 6, 18, 8, 1, 1, 1, ...
4 | 4, 16, 18, 3, 12, 2, 8, 9, 13, 6, 1, 1, 1, ...
5 | 5, 2, 10, 4, 20, 8, 17, 16, 11, 9, 22, 18, 21, 13, 19, 3, 15, 6, 7, 12, 14, 1, 1, 1, ...
6 | 6, 13, 9, 8, 2, 12, 3, 18, 16, 4, 1, 1, 1, ...
7 | 7, 3, 21, 9, 17, 4, 5, 12, 15, 13, 22, 16, 20, 2, 14, 6, 19, 18, 11, 8, 10, 1, 1, 1, ...
And so on; so I'm not doing all your work for you, I'm going to leave you the rest of the table to finish.
If you have access to a programming language, here's a nice little script (in Python, but easily translatable to other languages) that will print out the powers of g mod n for you (just plug in for g and n; you could even run a for loop over them):
x = g
while (x > 1):
print(x)
x = (x*g)%n
Or you can do it by hand of course. It's tedious, but not complicated.
Instead, I'm going to focus on the part that comes after you finish the table.
Notice how every number from 1 to 22 is somewhere in the table for powers of 5. That means 5 is a primitive root of 23.
The same is true of the powers of 7; so 7 is also a primitive root of 23.
Since you can get any number as a power of any primitive root, that means you can also get any other primitive root as a power of any primitive root.
We picked 5 as our favorite primitive root, so we want to express 7 as a power of 5. Read through the table, and you'll find that 7 = 5^19 mod 23.
You could just as well have chosen 7 as your favorite and found that 5 = 7^7 mod 23; but we were told to make 5 our favorite.
Hopefully you can take it from here. Complete the table; any rows that contain all numbers from 1 to 22 are primitive roots. Go back to the row for powers of 5 and find the column equal to that number; then you can express the new primitive root g as some power of 5.
No comments:
Post a Comment