Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
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. –  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
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. –  Jyrki Lahtonen Mar 7 '12 at 6:16
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$. –  Jyrki Lahtonen Mar 7 '12 at 6:24
2  
Without a computer, checking that $52578$ is prime would not be fun... –  Robert Israel Mar 7 '12 at 7:51
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.