0
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 1) The order of $59$ is a divisor of $70$. What does the given condition rule out? (It would be best if you asked one question at a time, and indicated what approach you tried.) $\endgroup$ – André Nicolas Nov 9 '15 at 6:54
  • 1
    $\begingroup$ In your proof for part 1. You cannot conclude the order greater than $46$ because the question does not state that the mutually incongruent elements are all not equal to $1$. The best you can conclude is it is greater than anything between $1$ and $46-11=35$. $\endgroup$ – cr001 Nov 9 '15 at 7:59
  • $\begingroup$ Oh ok, I'll look at that part again, thanks so much! $\endgroup$ – MathQuestion Nov 9 '15 at 8:57
0
$\begingroup$

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}$

$\endgroup$
  • $\begingroup$ Thanks, I think the first part for 2b was what I wasn't able to figure out at first... $\endgroup$ – MathQuestion Nov 9 '15 at 8:55
  • $\begingroup$ Yep that was the hard part of this problem :) $\endgroup$ – cr001 Nov 9 '15 at 9:09
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks so much, again 2 was the confusing part but I got it now. $\endgroup$ – MathQuestion Nov 9 '15 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.