I need to find all the primitive roots of 49. First note, $ ϕ(49) = 42 $
Is there an easier way to go about trying all numbers less than $42$ to find the primitive roots of $49$ if we already know that the primitive roots of $7$ and $49$ are $3$ and $5$?
Here is another way to see this, so you don't have to take as many powers as in azimut's answer.
Theorem. Suppose that $p$ is an odd prime. If $g\bmod p$ is a primitive root for $\mathbb{Z}/p\mathbb{Z}$ and $g^{p-1}\not\equiv 1 \bmod p^2$, then $g$ is also a primitive root of $p^2$. If $g^{p-1}\equiv 1 \bmod p^2$, then $g+p$ is a primitive root of $p^2$.
Now let's apply this result to your example, when $p=7$. In $\mathbb{Z}/7\mathbb{Z}$ there are $\phi(\phi(p))=\phi(6)=2$ primitive roots, namely $3$ and $5$. In $\mathbb{Z}/49\mathbb{Z}$ there are $\phi(\phi(49))=\phi(42)=\phi(6)\phi(7)=12$. If $h$ is a primitive root modulo $49$, then $h$ is also a primitive root modulo $7$, so $h\equiv 3$ or $5\bmod 7$. There are seven such $h\equiv 3$ and seven such $h\equiv 5\bmod 7$, so we have $14$ candidates for primitive roots, of which $12$ are primitive roots. By the theorem, those which are not primitive roots must satisfy $h^{p-1}\equiv 1 \bmod p^2$. Clearly $$(3^7)^6\equiv 3^{(7\cdot 6)}\equiv 1 \quad \text{ and } \quad (5^7)^6\equiv 5^{(7\cdot 6)}\equiv 1 \bmod 49,$$ by Euler's theorem, because $\phi(49)=42=7\cdot 6$. Since $3^7\equiv 3 \bmod 7$ and $5^7\equiv 5\bmod 7$, by Fermat's little theorem, we conclude that $3^7$ and $5^7$ are the two exceptions: $$3^7\equiv 31 \bmod 49, \quad \text{ and } \quad 5^7\equiv 19 \bmod 49.$$ Hence, the set of primitive roots modulo $49$ are: $$\{3+7k: 0\leq k\leq 6, k\neq 4\} \quad \text{ and } \quad \{5+7j: 0\leq j\leq 6, j\neq 2\}.$$
If you have found one primitive root $a$, you get all the primitive roots in the form $a^i$ where $\gcd(i,42) = 1$.
Since $\,\phi(49)=42\,$ , for some particular element $\,w\in\Bbb F_{49}^*\,$ one must check whether $\,w^k=1\,$ , for some divisor of $\,42\,$ smaller than $\,42\,$ itself.
For example (all is done modulo $\,49\,$):
$$5^2\neq 1\;,\;\;5^3=27\neq 1\;,\;\;5^6=43=27^2\neq 1\;,\;\;5^7=5\cdot43=5\cdot(-6)=-30\neq1$$
$$5^{14}=(-30)^2=18\neq 1\;,\;\;5^{21}=(-30)^3=-1\Longrightarrow \mathcal ord_{49}(5)=42$$
