Find ord2575.
Note that 257 is prime. Thus we know ϕ(257)=256=28. As the order of 257 must divide ϕ(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.