# Prove that $a^{b} \equiv 3 \,( \text{mod}\, 4)$ implies $a,b$ odd.

So far I've shown that $$a^{b} \equiv 3 \,( \text{mod} \, 4) \implies a^{b} \,\text{odd}\implies a \, \text{odd}$$. I also know that since $$a^{b} \equiv 3 \, (\text{mod} \, 4)$$, there exists prime $$p \mid a^{b}$$ such that $$p \equiv 3 \, (\text{mod} \, 4)$$.

Any help would be appreciated, thanks!

As you've shown, $$a$$ must be odd as any even value can't be congruent to $$3$$ modulo $$4$$. Thus, either $$a \equiv 1 \pmod 4$$, which doesn't work as $$a^b \equiv 1 \pmod 4$$ for any $$b$$, or $$a \equiv 3 \pmod 4$$. For the second case, note $$a^2 \equiv 3^2 \equiv 1 \pmod 4$$. Thus, for any even $$b = 2c$$ for some integer $$c$$, you have $$a^b \equiv (3^2)^c \equiv 1^c \equiv 1 \pmod 4$$.
This means $$b$$ must be odd. Note this gives that $$b = 2d + 1$$ for some $$d$$, so $$a^b \equiv (3^2)^d(3) \equiv 3 \pmod 4$$.