# Is this a legitimate proof? If not, how to prove?

Question: Determine all natural numbers $n$ such that: $7 \mid \left(3^n - 2\right) \implies3^{n}\equiv 2\pmod{7}$

Multiply both sides by 7

$7 \cdot 3^{n}\equiv 7\cdot2\pmod{7}$

Divide both sides by seven, since $\gcd(7,7) = 7$, we have to divide modulus by $7$

$\implies3^{n}\equiv 2\pmod{7/7}$

$\implies3^{n}\equiv 2\pmod{1}$

Therefore $n$ is any natural number, since one divides everything. But I made a mistake somewhere since the original equation doesn't work for $n = 1$

• Multiplying by $7$ reduces the equation to a triviality: The two expressions are obviously congruent modulo $7$ regardless of whether the original expressions were congruent or not. Anyway, your conclusion is that two numbers are congruent modulo $1$. Sure, why not? You concluded something true (and trivial). You did not show that the original equation was equivalent to it, only that it implies it. But anything (false or not) implies all true statements. So unfortunately you haven't really made any progress. Commented Dec 14, 2014 at 6:56
• That makes sense, for a moment there I thought I found a loophole but obviously not. Thanks! Commented Dec 14, 2014 at 7:00
• When you multiply the congruence by a number, for the congruence to be equivalent you'll have to multiply the modulus by the $\gcd$ of the modulus and the number you're multiplying by. Commented Dec 14, 2014 at 10:55

Noting that $n=1$ does not work, let $n \ge 2$. Then as $3^2 \equiv 2 \pmod 7$, we have the equivalent statement $$2\cdot 3^{n-2} \equiv 2 \pmod 7 \iff3^{n-2}\equiv 1 \pmod 7$$
Now that has solutions $n = 6k+2$ as $3^6$ is the smallest positive power of $3$ that is $\equiv 1 \pmod 7$, so the solution is for natural number s.t. $n = 2 \pmod 6$.
The remainders of $3^n\bmod 7$ starting from $n=1$ are: $$3,2,6,4,5,1,3,\cdots$$ And by Fermat's little theorem, $$3^{n+6}-2 \equiv 3^n-2\pmod 7$$