# Does Computing $\text{ord}_{52579}1001$ Require a Computer?

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!

-
$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. – user2468 Mar 7 '12 at 6:02
It may also help to point out that $1001 = 7 \cdot 11 \cdot 13$. – JavaMan Mar 7 '12 at 6:08
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. – Jyrki Lahtonen Mar 7 '12 at 6:16
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$. – Jyrki Lahtonen Mar 7 '12 at 6:24
Without a computer, checking that $52578$ is prime would not be fun... – Robert Israel Mar 7 '12 at 7:51