How do you work out the order of large integers?

Question

$\Bbb Z/420$. $143 [420]$. I do not know how you would go about working the order of this? I have already worked out $\phi(420)$ to equal $96$, so I know this means there are 96 units.

Answer 1

If $n,k\in\Bbb Z^+$, $a^{k}\equiv 1\pmod{n}$ and $p\mid k\implies a^{k/p}\not\equiv 1\pmod{n}$, then $\text{ord}_n(a)=k$.

In this case, it's enough to prove $143^{12}\equiv 1\pmod{420}$ and $143^{12/2}\not\equiv 1\pmod{420}$ and $143^{12/3}\not\equiv 1\pmod{420}$.

$420=2^2\cdot 3\cdot 5\cdot 7$. It's enough to prove $143^{12}\equiv 1\pmod{2^2,3,5,7}$ and $143^{12/2}\equiv -1\pmod{5}$ and $143^{12/3}\equiv 4\pmod{7}$.

Answer 2

Use Carmichael Function $\lambda(420)=\cdots=12$

So for any integer $a, (a,420)=1;$ $$a^{12}\equiv1\pmod{420}\ \ \ \ (1)\implies\text{ord}_{420}a\mid12$$

Now $420=3\cdot5\cdot7\cdot4;$

$143\equiv3\pmod7\implies143^3\equiv3^3\equiv-1\pmod7$

$\implies$ord$_73=6\implies$ord$_{420}143$ will be multiple of $6$

Similarly, ord$_5143=4\implies$ord$_{420}143$ will be multiple of $4$

$\implies$ord$_{420}143$ will be multiple of lcm$(4,6)=12$

Can you use $(1)$ now?