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

310 Views Asked by At

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$

2

There are 2 best solutions below

1
On BEST ANSWER

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$.

0
On

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$$