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) 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}$
No comments:
Post a Comment