0
$\begingroup$

I have two questions:

Q1: Why is the order of $19$ modulo $29$ equal to $28$? We know by Fermat's Little Theorem that $a^{28} \equiv 1 \pmod{29}$, but why is $28$ the smallest here?

Q2: Let $\left(\dfrac{a}{p}\right)$ denote the Legendre symbol. Is there any reason why $\left(\dfrac{19}{29}\right) = -1$ and using Euler's criterion $19^{14} \equiv -1 \pmod{29}$ gives that $14$ is the smallest such power that $19$ can be raised to to be $-1$ modulo $29$? Why is it the smallest? I think this may be related to question one.

$\endgroup$
  • $\begingroup$ The possible orders, $\pmod {29}$ are $\{1,2,4,7,14,28\}$. Pretty easy to just check each... $\endgroup$ – lulu Jul 26 '16 at 22:53
  • $\begingroup$ It is true that $a^{28}\equiv1\pmod{29}$ is not enough to deduce that the order of $19$ modulo $29$ is exactly $28$; indeed, that congruence is equivalent to saying that that order divides $28$. It's also true that $19^{14}\equiv-1\pmod{29}$ is not enough to conclude that $14$ is the smallest such exponent. For example, $12^{14}\equiv-1\pmod{29}$, but here $14$ isn't the smallest such exponent, as $12^{2}\equiv-1\pmod{29}$ also. In short, one needs to use additional information to conclude that $28$ is the order in Q1 and that $14$ is the smallest such exponent in Q2. $\endgroup$ – Greg Martin Jul 26 '16 at 22:57
  • $\begingroup$ @lulu Any idea about Q2? $\endgroup$ – John Ryan Jul 26 '16 at 22:58
  • $\begingroup$ $a^k\equiv -1\pmod n\implies a^{2k}\equiv 1\pmod n$, so if you could lower $14$ in part $2$ you could lower $28$ in part $1$. $\endgroup$ – lulu Jul 26 '16 at 23:01
  • $\begingroup$ @lulu I don't see how. $\endgroup$ – John Ryan Jul 26 '16 at 23:04
1
$\begingroup$

By the Order Test, $\,19\,$ has order $28\iff 19^4\not\equiv 1\not\equiv 19^{14}\!\pmod{29},\,$ which is true:

$$19^2\equiv 13,\,\ \color{#0a0}{19^4}\equiv 13^2\equiv \color{#0a0}{-5},\,\ \smash[b]{\underbrace{19^{14}\!\equiv 19^2 (\color{#0a0}{19^4})^3 \equiv 13 (\color{#0a0}{-5})^3\equiv 13(-9)\equiv -1}}$$

Of course we can omit the calculation of $\ 19^{14}\,$ if we know it from the Legendre symbol.


Order Test $\,\ \,a\,$ has order $\,n\iff a^n \equiv 1\,$ but $\,a^{n/p} \not\equiv 1\,$ for every prime $\,p\mid n.\,$

Proof $\ (\Leftarrow)\ $ If $\,a\,$ has $\,\rm\color{#c00}{order\ k}\,$ then $\,k\mid n.\,$ But if $\,k < n\,$ then $\,k\,$ is proper divisor of $\,n\,$ hence, by uniqueness of prime factorizations, $\,k\,$ arises by deleting at least one prime $\,p\,$ from the factorization of $\,n,\,$ so $\,k\mid n/p,\,$ say $\, kj = n/p,\,$ so $\,a^{n/p}\! \equiv (\color{#c00}{a^k})^j\equiv \color{#c00}1^j\equiv 1,\,$ contra hypothesis. $\ (\Rightarrow)\ $ By definition of order.

$\endgroup$
0
$\begingroup$

For Q1, the comments tell you what to check but not why. Since I see you have posted with the abstract algebra tag before, it is worth knowing.

The order of an element must divide the order of a group. The multiplicative group of integers modulo 29 has order $29-1=28$ because 29 is a prime. In general the multiplicative group of integers modulo $n$ as order $\phi(n)$, where $\phi$ is Euler's totient function.

This is why it suffices to check the other numbers that divide 28.

$\endgroup$
0
$\begingroup$

Q1: If it happened for a smaller exponent, this exponent would be a strict divisor of$28$, hence it would be $2$, $4$, $7$ or $14$. In any case, we'd have $19^{14}\equiv 1 $ since 14 is multiple of each. As $14$ is event and $\mathbf Z/29\mathbf Z$ is a field, this would imply $19^7\equiv\pm 1$. Now the fast exponentiation algorithm shows it is equal to $12$.

Q2: Use the laws of quadratic reciprocity: $$\Bigl(\frac{19}{29}\Bigr)=\Bigl(\frac{29}{19}\Bigr)(-1)^{9\cdot14}=\Bigl(\frac{29\bmod 19}{19}\Bigr)=\Bigl(\frac{10}{19}\Bigr)=\Bigl(\frac{2}{19}\Bigr)\Bigl(\frac{5}{19}\Bigr)=-\Bigl(\frac{5}{19}\Bigr)$$ because $19\equiv 3\mod 8\;$ (2nd supplementary law), and finally $$\Bigl(\frac{5}{19}\Bigr)=\Bigl(\frac{19}{5}\Bigr)(-1)^{9\cdot 2}=\Bigl(\frac{19}{5}\Bigr)=\Bigl(\frac{19\bmod5}{5}\Bigr)=\Bigl(\frac{4}{5}\Bigr)=1.$$

$\endgroup$

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.