Timeline for Can the order of a rational number in Z/pZ be as large as we want
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 5, 2012 at 23:47 | vote | accept | Xiaolei Wu | ||
| Oct 3, 2012 at 9:53 | comment | added | Felipe Voloch | $\log p / \log \max \{|d_1|,|d_2|\}$ is what I should have written. The max is at least two, but that's irrelevant. | |
| Oct 3, 2012 at 9:47 | history | edited | Charles Matthews | CC BY-SA 3.0 |
edit title
|
| Oct 3, 2012 at 4:04 | comment | added | David Feldman | Rather than close the question, why not edit so as to ask for the best known upper bound (in terms of $n$) on the smallest possible $p$? Subexponential? | |
| Oct 3, 2012 at 3:41 | history | made wiki | Post Made Community Wiki by Xiaolei Wu | ||
| Oct 3, 2012 at 3:29 | comment | added | Xiaolei Wu | Thank you, Douglas Zare. I see your proof now. I think I am going to close this question soon since it is actually very easy. | |
| Oct 3, 2012 at 3:20 | comment | added | Xiaolei Wu | Hi, Felipe. I actually think you are wrong now. There are always elements in Z/pZ has order 2 since the multiplicative group has order p-1 which is an even number if p is odd. | |
| Oct 3, 2012 at 3:19 | answer | added | S. Carnahan♦ | timeline score: 1 | |
| Oct 3, 2012 at 3:08 | comment | added | Douglas Zare | I'm not sure how Felipe got $\log p / \log 2$, but if $d_1^m \equiv d_2^m \mod p$ then $|d_1^m - d_2^m| = p k \ge p$. So, at least one of $|d_1|^m, |d_2|^m$ has to be at least $p$. Choosing $p$ larger than $\max(|d_1|,|d_2|)^m$ means the order has to be greater than $m$. | |
| Oct 3, 2012 at 2:56 | comment | added | Xiaolei Wu | Hi, Felipe, how do you see the order is at least logp/log2? I am not a number theorist, so I might be a little slow on this. | |
| Oct 3, 2012 at 2:55 | history | edited | Xiaolei Wu | CC BY-SA 3.0 |
added 30 characters in body
|
| Oct 3, 2012 at 2:48 | comment | added | Felipe Voloch | If $d_1/d_2 \ne \pm 1$, the order $\mod p$ is clearly at least $\log p/\log 2$, so yes. | |
| Oct 3, 2012 at 2:40 | history | asked | Xiaolei Wu | CC BY-SA 3.0 |