2
$\begingroup$

Our professor is abusing us: He wants us to compute $$\text{ord}_{52579}2\text{, ord}_{52579}3\text{, and ord}_{52579}1001.$$ Recall that the least positive integer $x$ such that $a^x\equiv1\pmod{n}$ is denoted $\text{ord}_na$.

I have a feeling that I may need to use a computer, but I do not have such computing power currently at my disposal. :(

Does anyone know of an anlytical approach to this? Thanks!

  • 6
    $52579$ is a prime. So the order of a nonzero element $\bmod 52579$ is a divisor of $52579-1$. There are $24$ divisors of $52578$: [Wolfram|Alpha](http://www.wolframalpha.com/input/?i=ifactors%2852578%29).2012-03-07
  • 0
    It may also help to point out that $1001 = 7 \cdot 11 \cdot 13$.2012-03-07
  • 1
    Well, $p=52579$ is a prime, and $p-1=2\cdot3^2\cdot23\cdot127$, so there aren't that many alternatives. Quadratic reciprocity tells you that all of $2,3,7,13$ are non-QRs modulo $p$, but $11$ is a QR modulo $p$. Thus the orders of $2$ and $3$ are even, and the order of $1001$ is odd. If your calculator can handle ten digits, then repeated squaring will help - but I still feel for you.2012-03-07
  • 1
    As a first test check whether $a^{(p-1)/q}\equiv 1\pmod p$ for some prime divisor $q$ of $p-1$. If not, then you can conclude that $a$ has order $p-1$. If you know that $a$ is a quadratic residue, then you can skip $q=2$, and instead check whether any of the powers $a^{(p-1)/(2q)}$ is congruent to $1\pmod p$. If not, then you can similarly conclude that the order must be $(p-1)/2$.2012-03-07
  • 2
    Without a computer, checking that $52578$ is prime would not be fun...2012-03-07
  • 0
    @Robert Israel: I think you mean 52579.2012-03-07

0 Answers 0