Proof that $3^n$ is never congruent to $7 \bmod 1000$

Question

I’ve been reading Mathematics Galore! by James Tanton. He has a brief elegant and accessible proof of the existence of a power of 3 that ends in 001. He then asks if a power of 3 ever ends in 007.

This is equivalent to asking if $3^n = 7 \bmod1000$.

I can brute force the answer using WolframAlpha but cannot figure out an elegant proof.

This question has been driving me nuts for about a month now. Any help is greatly appreciated.

$3^n$ is congruent to $3$ or $1$ modulo $8$. – Angina Seng Jun 29 '19 at 16:00 — Angina Seng, Jun 29 '19 at 16:00

score 4 · Accepted Answer · answered Jun 29 '19 at 17:01

4

Suppose $3^n\equiv7\bmod1000$, then $3^n\equiv7\bmod8$ as $8\mid1000$. But calculating the powers of $3$ modulo $8$ only gives $1,3,1,3\dots$ alternating; $7$ never appears. Thus no power of $3$ ends in $007$.

answered Jun 29 '19 at 17:01

Parcly Taxel

103,344

Proof that $3^n$ is never congruent to $7 \bmod 1000$

1 Answers1