Why Are There No Solutions To $2^x \equiv 3\pmod{9}$? I know this congruence has no solutions because $\gcd(3,9) \ne 1$. I would like to understand why this gcd restriction is needed for solvability. Thanks!
 A: At a more elementary level, this is essentially just the definition ; if $2^x \equiv 3 \pmod 9$, then there exists $k \in \mathbb Z$ such that $2^x-3 = 9k$, i.e. $2^x = 3+9k$. You can either see directly that this cannot be possible, or you can recall the definition of the g.c.d. that it is the smallest positive $\mathbb Z$-linear combination of $3$ and $9$, i.e. the smallest positive integer of the form $3m + 9k$ ; the g.c.d. divides all such linear combinations. Since in this case $(3,9) = 3$, if such a $k$ with $2^x = 3+9k$ would exist, we would have $(3,9)$ dividing $2^x$, a contradiction.
Hope that helps,
A: If $2^x\equiv 3\pmod{9}$, then $9|(2^x-3)$, and in particular $3|(2^x-3)$.  But also $3|3$, so $3|(3+(2^x-3))$, so $3|2^x$.  This is impossible.
A: The crucial thing to note here is that if $\gcd(a,c)=1$ and $\gcd(b,c)=1$, then so must $\gcd(ab,c)=1$ - that is to say, the product of any two numbers coprime to a third is still coprime to the third. This is crucial in proving that the elements of $\mathbb Z/ c\mathbb Z$ coprime to $c$ form a group under multiplication (and are, in particular, closed under multiplication). Since (the equivalence class of) $2$ is in this group, but $3$ is not, no power of $2$ will ever be congruent to $3$.
To apply this fact more directly, notice that it implies that $\gcd(2^n,9)=1$ for all $n\in\mathbb N$. Since $\gcd(3+9k,9)=3$, it follows that $2^n$ is never of the form $3+9k$ and thus never congruent to $3$ mod $9$.
A: Hint $\ $ If $\, \color{#0a0}m\mid a^n-\color{#c00}b\,$ and  $(b,m)> 1\,$ then a prime $\,p\mid \color{#c00}b,\color{#0a0}m$  $\,\,\Rightarrow\,p\mid a^n\,\Rightarrow\,p\mid a\,\Rightarrow\,(a,b,m)>1$
A: if $2^x \equiv_9 3$ then $2^{2x} = 4^x \equiv_9 0$ so $4^x$ must be a multiple of $9$.
but since $4^3 \equiv_9  1$ then for any integer $n$ we have $4^{3n} \equiv_9 1$ giving $4^{3n+1} \equiv_9 4$ and $4^{3n+2} \equiv_9 7$
A: If you are talking about when $x$ is an integer, it's quite simple.
We can write $9m+3$ as $3n$ where $m$ and $n$ are integers.
Obviously, $2^{x}$ can't be divisible by $3$. Hence, we can say that $2^{x}\neq 9m+3$.
