Processing math: 4%
     

Exercises - The Order of an Integer and Primitive Roots

  1. 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.

  2. 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.

  3. 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.

  4. Suppose n is a positive integer, and a^{-1} is a multiplicative inverse of a\pmod{n}.

    1. Show \textrm{ord}_n a = \textrm{ord}_n (a^{-1})
    2. If a is a primitive root modulo n, must a^{-1} also be a primitive root?

    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.

  5. 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}.

  6. 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.

  7. 🔎 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.