Number Theory: Modular Arithmetic Orders and Primitive Roots

Question

I have these homework problems that I haven't been able to figure out:

1) If the set $\{ 59,59^2,\dots,59^{11} \}$ has mutually incongruent elements mod $71$, what could $o_{71}(59)$ be? If also $\{ 59^{11},59^{12},\dots,59^{46} \}$ has mutually incongruent elements mod $71$, what is $o_{71}(59)$.

2) Assume that $5$ is a primitive root of $73$. What is the minimal $k>3$ satisfying $5^k\equiv 125\pmod{73}$? Show that $x^m\equiv 3,125\pmod{73}$ has a solution $\iff\gcd(m,6)=1$.

Thanks in advance, any help is appreciated!

#1 Proof

Note that $o_{71}(59)$ must divide $\phi(71)=70$ and that if any power of $59$ is congruent to $1$ modulo $71$, then the subsequent power is congruent to $59$ modulo $71$.

Therefore, since $\{59,59^2,\dots,59^{11}\}$ contains mutually incongruent elements, no element in this set can be congruent to $1$ modulo $71$ as this would mean that the next element would have to be congruent to $59$ also (Note also that $59^{11}\not\equiv 1\pmod{71}$ since $11\not\mid 70$).

Thus $o_{71}(59)>11$. Since the only numbers greater than $11$ that divide $70$ are $14,35,$ and $70$, the order of $59$ modulo $71$ must be $14,35,$ or $70$.

By similar reasoning, if $\{59^{11},59^{12},\dots,59^{46}\}$ contains mutually incongruent elements, then no element in this set can be congruent to $1$ modulo $71$ (note also that $46\not\mid 70\implies 59^{46}\not\equiv 1\pmod{71}$), so the order of $59$ modulo $71$ must be greater than $46$.

But the only divisor of $70$ greater than $46$ is $70$ itself, so we must have $o_{71}(59)=70$. $\blacksquare$

#2 Proof

Note that $73$ is prime, so $\phi(73)=72$. Hence, since $5$ is a primitive root of $73$, we must have $5^{72}\equiv 1\pmod{73}$.

But this implies that the elements of $\{5,5^2,5^3,\dots,5^{72}\}$ are mutually incongruent modulo $73$ and that the elements of this set are congruent to $1,2,3,\dots,72$ in some order. Therefore since $5^3=125\equiv 52\pmod{73}$, no other element in this set is congruent to $125$ modulo $73$.

So, we must have $k>72$. But $5^{72}\equiv 1\pmod{73}\implies 5^{72}\cdot 5^3\equiv 1\cdot 5^3\pmod{73}\implies 5^{75}\equiv 125\pmod{73}$. Hence, the minimal $k>3$ satisfying $5^k\equiv 125\pmod{73}$ is $k=75$.

But I'm still not very sure how to prove the second part of $2$...

Answer 1

1) It means $o_{71}(59)$ cannot be $1$ to $10$ and for the second set it means it cannot be $1$ to $35$.

By fermat little theorem we know $59^{70}\equiv1\pmod{71}$. If there would be another $59^x\equiv1\pmod{71}$ where $x<70$ then we have $59^{70-x}\equiv1$ as well, forcing there exist such an $x\leq 35$, contradicting what we have: $o_{71}(59)$ must be greater than $35$.

2a) Knowing $5$ is a primitive root, we know the order of $5$ is $72$ combining with fermat little theorem, otherwise is the order is less than $72$ we would have at least one remainder not obtainable by powers of $5$ contradicting the primitive root definition.

Hence $k=3+72=75$ is the smallest $k$.

2b)

Forward direction:

First we need to prove $o(3125)=72$. Suppose there is an $x$ that $3125^x\equiv1\pmod{73}$ then $5^{5x}\equiv1\pmod{73}$ hence $72\mid5x\implies 72\mid x$. Hence $o(59)=o(3125)=72$

Suppose $x^m\equiv3125\pmod{73}$ and $gcd(m,6)\neq 1$. Since $x^{72}\equiv1\pmod{73}$ we can find a $t<72$, namely $t={72\over gcd(m,6)}$ such that $x^{mt}\equiv 1\pmod{73}$ or $59^t\equiv1\pmod{73}$ where $t<72$ contradicting $o(59)=72$.

Backward direction:

Suppose $gcd(m,6)=1$ then we have $gcd(m,72)=1$ and there exist $a,b$ that $ma-72b=1$

Since $3125\equiv59\pmod{73}$ and $59^{72}\equiv1\pmod{73}$

Let $x=59^{a}$ then $x^m=59^{ma}=59^{72b+1}\equiv59\pmod{73}$

Answer 2

For 1), since the set $\{59,59^2,\dots, 59^{11}\}$ has mutually incongruent elements mod $71$ it can't contain $1$ (why is this?). Hence the order of $59$ is greater than $11$. On the other hand, the order has to divide the order of the multiplicative group which is $70$. The only divisors of $70$ larger than $11$ are $14,35,70$. The second case can be solved in the same way.

For 2), since $5$ is a primitive root mod $73$, we have $5^{72}\equiv 1$ (mod $73$) and no smaller power of $5$ will equal $1$ (mod $73$). So the next time $5^k=125$ is when you have gone through every other number mod $73$.