| | |
Find $\text{ord}_{257} 5$.
Note that $257$ is prime. Thus we know $\phi(257) = 256 = 2^8$. As the order of $257$ must divide $\phi(257)$, our answer must be a power of $2$. As such, successive squaring$\pmod{257}$ reveals the order quickly:
$$\begin{align*} 5^1 &\equiv 5\pmod{257}\\ 5^2 &\equiv 25\\ 5^4 &\equiv 111\\ 5^8 &\equiv 242\\ 5^{16} &\equiv 225\\ 5^{32} &\equiv 253\\ 5^{64} &\equiv 16\\ 5^{128} &\equiv 256\\ 5^{256} &\equiv 1 \end{align*}$$ In this case, it appears that $\textrm{ord}_{257} 5$ actually equals $\phi(257) = 256$. This of course makes $5$ a primitive root modulo $257$.Show that $2$ is a primitive root modulo $11$.
As $\phi(11) = 10$, the order of $2\pmod{11}$ must divide $10$. So we check $2^2 \equiv 4\pmod{11}$ and $2^5 \equiv 10\pmod{11}$. Since neither of these are $1$, and we know $2^{\phi(11)} = 2^{10} \equiv 1\pmod{11}$ by Euler's Theorem, we have $\textrm{ord}_{11} 2 = \phi(11)$, making $2$ a primitive root modulo $11$.
How many incongruent primitive roots does 14 have?
Two. ($3$ and $5$). Throwing out even integers and $7$ as they share common factors with $14$ leaves $1,3,5,9,11,\textrm{ and } 11$. Trivially, the order of $1$ is $1$, and the order of $13$ is $2$. The order for $9$ and $11$ are quickly found to both be $3$. Only the order of $3$ and $5$ are found to be $\phi(14) = 6$, making them primitive roots.
Suppose $n$ is a positive integer, and $a^{-1}$ is a multiplicative inverse of $a\pmod{n}$.
Suppose $\textrm{ord}_n a = k$. Then $a^k \equiv 1\pmod{n}$ and $a^t \not\equiv 1\pmod{n}$ for any $t \lt k$. Multiplying both sides of the first congruence $k$ times by $a^{-1}$ tells us that $1 \equiv (a^{-1})^k\pmod{n}$, So $\textrm{ord}_n a^{-1} \mid k$. However, if $(a^{-1})^t \equiv 1\pmod{n}$ for any $t \lt k$, we can multiply both sides $t$ times by $a$ to obtain $a^t \equiv 1\pmod{n}$ which is impossible. Thus, the first power of $a^{-1}$ congruent to $1\pmod{n}$ is $k$ and we have $\textrm{ord}_n a = \textrm{ord}_n (a^{-1})$.
By part (a), if $a$ is a primitive root modulo $n$, then $\textrm{ord}_n a = \phi(n) = \textrm{ord}_n a^{-1}$. Consequently $a^{-1}$ is also a primitive root modulo $n$.
Show if $n$ is a positive integer relatively prime to integer $a$ and $\textrm{ord}_{n} a = st$, then $\textrm{ord}_{n} a^t = s$.
Note that $\textrm{ord}_{n} a = st$ requires $a^{st} \equiv 1\pmod{n}$, which implies $(a^t)^s \equiv 1\pmod{n}$.
Now suppose that for some $k \lt s$ we have $(a^t)^k \equiv 1\pmod{n}$. Then $a^{kt} \equiv 1\pmod{n}$. But this is impossible as if $k \lt s$, then $kt \lt st$ which contradicts the stated order of $a$ modulo $n$.
Thus $s$ is the minimum positive exponent on $a^t$ that produces a $1\pmod{n}$. Equivalently, $(a^t)^s \equiv 1\pmod{n}$.
Show if $\gcd (a,n) = \gcd (b,n) = \gcd (\textrm{ord}_n a, \textrm{ord}_n b) = 1$, then $\textrm{ord}_n (ab) = (\textrm{ord}_n a)(\textrm{ord}_n b)$.
For convenience, suppose $$\begin{array}{rcl} x &=& \textrm{ord}_n a\\ y &=& \textrm{ord}_n b\\ z &=& \textrm{ord}_n (ab) \end{array}$$
We then need to show $z=xy$ under the conditions given.
We will argue that $z | xy$ and $xy | z$, which taken together gives us the desired result.
To show the first statement holds, note that $$(ab)^{xy} \equiv (a^x)^y \cdot (b^y)^x \equiv 1^y \cdot 1^x \equiv 1\pmod{n}$$ As such, the initial exponent on $ab$ must be a multiple of $\textrm{ord}_n (ab)$.
Showing the second statement holds requires a little bit more work...
Our intention will be to show that $x | z$ and $y | z$. Then, since we were told that $x$ and $y$ are relatively prime, it will have to be the case that $xy | z$.
First, we argue that $y | z$.
We know $(ab)^z \equiv 1\pmod{n}$. Thus, $(ab)^{xz} \equiv 1\pmod{n}$ as well.
Rewriting things a bit, we have $$a^{xz} \cdot b^{xz} \equiv 1\pmod{n}$$
However, $a^{xz} \equiv (a^x)^z \equiv 1^z \equiv 1\pmod{n}$, so the previous congruence reduces to $$b^{xz} \equiv 1\pmod{n}$$
Of course, this requires the exponent on $b$ must be a multiple of $\textrm{ord}_n b$. Equivalently, $y | xz$.
Since $x$ and $y$ are relatively prime, it must be the case that $y | z$.
Arguing $x | z$ is done in a similar manner.
We know $(ab)^z \equiv 1\pmod{n}$. So, $(ab)^{yz} \equiv 1\pmod{n}$.
Thus, $a^{yz} \cdot b^{yz} \equiv 1\pmod{n}$, and noting that $b^{yz} \equiv (b^y)^z \equiv 1^z \equiv 1\pmod{n}$, we have $a^{yz} \equiv 1\pmod{n}$.
The exponent $yz$ must then be a multiple of $\textrm{ord}_n a$, so $x | yz$.
This, upon remembering that $x$ and $y$ are relatively prime, tells us that $x | z$.As hoped for, we have $x|z$ and $y|z$ with $x$ and $y$ relatively prime. Consequently $xy|z$.
Since we have now argued that $xy|z$ and $z|xy$, it can only be the case that $z=xy$.
Replacing $x$, $y$, and $z$ with their defining expressions, we arrive at the desired result, $$\textrm{ord}_n (ab) = (\textrm{ord}_n a)(\textrm{ord}_n b)$$
QED.
🔎 Gauss proved that there is always a primitive root for any prime modulus. Use this to prove that if $n$ is a Carmichael number, then for every prime $p$ dividing $n$, it must be the case that $(p-1) \mid (n-1)$.
You will need to appeal to both the Chinese Remainder Theorem, and the fact that Carmichael numbers are square-free.