2

The following is a question I've come across, which states:

Determine the smallest integer $k$ such that $4^k \equiv 1 \pmod{19}$.

We know that, according to Fermat's Little Theorem, $a^{p-1}\equiv 1 \pmod{p}$, and because $19$ is prime, it must be that $4^{19-1}\equiv 1$; in other words, $k=18$.

However, this is not the smallest solution - the smallest solution is $9$. I don't know how to find the smallest solution, though I would assume it has to do with the answer of $k=18$ somehow.

Any help would be appreciated.

Cisplatin
  • 4,675
  • 7
  • 33
  • 58

3 Answers3

1

Fermat's Little Theorem states, $a^{pāˆ’1}\equiv1(\mod p)$ for any prime $p$. So $2^{18}\equiv1(\mod 19)\implies (2^2)^9\equiv1(\mod 19)\implies4^9\equiv1(\mod 19)$. Therefore, $o(4)\underline<9$ in $\mathbb{Z}^{^*}_{19}$ such that $o(4)$ divides $9$, which implies $o(4)$ can take values $1,3$ or $9$. But $4\not\equiv1(\mod 19)$ & $4^3\not\equiv1(\mod 19)$ so, $o(4)=9$ in $\mathbb{Z}^{^*}_p$ ,i.e $9$ is the smallest integer such that $4^9\equiv1(\mod 19).$

Adhikary
  • 104
0

Recall that the set

$\quad {\displaystyle {\mathbb {Z} /19\mathbb {Z}}^{\,*} = \mathbb {Z} /19\mathbb {Z} \setminus \{0\}}$

forms a group under multiplication and contains $18$ elements. It follows from Lagrange's theorem that the order of any element in ${\displaystyle {\mathbb {Z} /19\mathbb {Z}}^{\,*}}$ must divide $18$ and belong to the set $\{1,2,3,6,9,18\}$.

We begin by determining the order of $[2]$.

Since $2^6 \equiv 2^4 \, 2^2 \equiv (-3) (4) \equiv 7 \pmod{19}$, the order of $[2]$ can't be $6$, and since $2 \mid 6$ and $3 \mid 6$, the order of $[2]$ must be either $9$ or $18$.

Since $2^9 \equiv 2^4 \, 2^4 \, 2^1 \equiv (-3) (-3) (2) \equiv 18 \pmod{19}$, the order of $[2]$ must be equal to $18$.

Let $k$ be the order of $[4]$. Then $1 \equiv 4^k \equiv 2^{2k} \pmod{19}$, so $2k \ge 18$ and therefore $k \ge 9$.

Also, $4^9 \equiv 2^{18} \equiv 1 \pmod{19}$ and therefore $k \le 9$.

We conclude that the order of $[4]$ is equal to $9$.

CopyPasteIt
  • 11,366
0

If this is a homework question you may be expected to be "clever" (!). However you can also quite simply use brute force, for ex. with Mathematica : 

Table[Mod[4^k, 19], {k, 1, 10}]

the output is

{4, 16, 7, 9, 17, 11, 6, 5, 1, 4}

thus $k=9$. (Excel should do it just as well, at least for $k$ not too large). Now, if you test values of $k$ up to, say, 100, you notice that it works for all multiples of 9...

Select[Range[100], Mod[4^#, 19] == 1 &]

output

{9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99}
A.G.
  • 2,781