# Fermat's Little Theorem and Legendre symbol

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.

• The possible orders, $\pmod {29}$ are $\{1,2,4,7,14,28\}$. Pretty easy to just check each... – lulu Jul 26 '16 at 22:53
• 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. – Greg Martin Jul 26 '16 at 22:57
• @lulu Any idea about Q2? – John Ryan Jul 26 '16 at 22:58
• $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$. – lulu Jul 26 '16 at 23:01
• @lulu I don't see how. – John Ryan Jul 26 '16 at 23:04

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.

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.

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.$$