Suppose that $q = p^n$ where p is a prime. Now assume that $q \equiv 1$ (mod $l$), where $l$ is a different prime, and that $q \not\equiv 1$ (mod $l^2$). How would I find the multiplicative order of $q$ (mod $l^k$) for arbitrary $k$? So far I have deduced (maybe wrongly) that the order of $q$ in $(\mathbb{Z}/l^2\mathbb{Z})^{\times}$ is $l$ but I don't know how to generalize the result.
[Math] Order of a prime power modulo a prime power
modular arithmeticnumber theory
Best Answer
$q$ can be any integer. I'll denote $q$ by $n$ and $l$ by $p$.
You want to prove that if $n\equiv 1\pmod{p}$ and $n\not\equiv 1\pmod{p^2}$, then:
if $p$ is odd, then $\text{ord}_{p^k}(n)=p^{k-1}$ for all $k\ge 1$.
if $p=2$, then $\text{ord}_{2^k}(n)=2^{k-2}$ for all $k\ge 3$, and $\text{ord}_{2^2}(n)=2$, $\text{ord}_2(n)=1$.
First I'll prove it for odd $p$. In the end of the answer I'll prove it for $p=2$.
The most straightforward way is just citing Lifting The Exponent Lemma (LTE), but you don't need it and I won't use it. If you're interested, I separately showed how to use it later in the answer.
Let $\upsilon_p(n)$ denote the exponent of the largest power of $p$ that divides $n$.
Lemma $1$: If $k\ge 1$, $p$ odd prime, $a\equiv 1\pmod{p^k}$, then $a^p\equiv 1\pmod{p^{k+1}}$.
Proof: $a^p-1=(a-1)\left(a^{p-1}+a^{p-2}+\cdots+1\right)$. $$a^{p-1}+a^{p-2}+\cdots+\equiv 1^{p-1}+1^{p-2}+\cdots+1\equiv p\equiv 0\pmod{p}\ \square$$
Lemma $2$: If $k\ge 1$, $p$ odd prime, $a^p\equiv 1\pmod{p^{k+1}}$, then $a\equiv 1\pmod{p^k}$.
Proof: $a^p-1=(a-1)\left(a^{p-1}+a^{p-2}+\cdots+1\right)$.
By Fermat's Little theorem $a\equiv 1\pmod{p}$. Let $a=pt+1$. Then it's enough to prove that $$p^2\nmid a^{p-1}+a^{p-2}+\cdots+1$$
$$=(pt+1)^{p-1}+(pt+1)^{p-2}+\cdots+1$$
Use the Binomial theorem:
$$\equiv ((p-1)pt+1)+((p-2)pt+1)+\cdots+((p-p)pt+1)\pmod{p^2}$$
$$\equiv (-pt-2pt-\cdots-ppt)+p\equiv p\left(\frac{-tp(p+1)}{2}+1\right)\equiv p\not\equiv 0\pmod{p^2}\ \square$$
You're given $\upsilon_p(n-1)=1$. From Lemmas $1$, $2$ follows $\upsilon_p\left(n^{p^k}-1\right)=k+1$.
Let's prove that $\text{ord}_{p^k}(n)=p^{k-1}$ for all $k\ge 1$, $p$ odd prime.
It's true if $k=1$. If $k\ge 2$, then $\upsilon_p\left(n^{p^{k-2}}-1\right)=p^{k-1}$, so $p^k\nmid n^{p^{k-2}}-1$.
Also $\upsilon_p\left(n^{p^{k-1}}-1\right)=p^k$, so $p^k\mid n^{p^{k-1}}-1$. The answer follows (see Lemma $3$).
Lemma $3$: If $x^k\equiv 1\pmod{m}$, then $\text{ord}_m(x)\mid k$.
Proof: Hint: For contradiction, let $k=\text{ord}_m(x)h+r$ with $0<r<\text{ord}_m(x)$ and get $x^r\equiv 1\pmod{m}$, contradiction.
The following is one of the Lifting The Exponent (LTE) Lemmas:
Therefore $\upsilon_p(n-1)=1\implies \upsilon_p\left(n^{p^k}-1\right)=k+1$ for all $k\ge 1$, $p$ odd prime.
If $p=2$, then you're given $n\equiv 3\pmod{4}$ and you want to prove $\text{ord}_{2^k}(n)=2^{k-2}$ for all $k\ge 3$ and $\text{ord}_{2^2}(n)=2$, $\text{ord}_{2}(n)=1$.
Theorem: If $a$ is odd, $a\not\equiv 1\pmod{8}$, $k\ge 3$, then $\text{ord}_{2^k}(a)=2^{k-2}$.
I proved it in this answer.