# Squares of primes in the sequence 7 + 6k

I was bored one day, and I stumbled across the fact that for the first few primes p (p >= 7 at least), have the fact that p^2 = 7 + 6k for some integer k. I couldn't prove it for all primes p >= 7 quickly (made a few stabs in the dark, but no luck), and I was wondering if this is a trivial fact and I'm missing something obvious? If not, are there any papers regarding representations of p^n, p prime, n an integer (preferably greater than 1)?

-
Looks better as $p^2=1+6n$ for some integer $n$. So we want to prove that $p^2$ has remainder $1$ on division by $6$, or equivalently remainder $1$ on division by $2$ and also on division by $3$. On division by $2$ is obvious. What about on division by $3$? – André Nicolas Dec 22 '11 at 6:06
+1 for relieving boredom with mathematical conjectures! – Jonas Meyer Dec 22 '11 at 6:17

Every prime number greater than $3$ has the form $1+6k$ or $5+6k$ for some integer $k$. The reason is that $6k$, $2+6k$, and $4+6k$ are even, and $6k$, $3+6k$ are divisible by $3$. Every number has to be of the form $j+6k$ for some $j\in\{0,1,2,3,4,5\}$, so this covers all cases.

So when you square a prime greater than $3$, you get $(1+6k)^2=1+6(2k+6k^2)$, or $(5+6k)^2=1+6(4+10k+6k^2)$. In either case, this shows that the square of a prime number greater than $3$ has the form $1+6j$ for some integer $j$. Notice that $1+6j=7+6(j-1)$, so this implies the result you observed.

-
 +1 for beating me by a few seconds. – user21436 Dec 22 '11 at 6:10 Could have avoided that tediousness if $5 (6)$ was interpreted as $-1 (6)$ – user21436 Dec 22 '11 at 6:12 @KannappanSampath: Good point. I was naïvely keeping things in the usual remainder after division by $6$ form, so I used $5$ without thinking much of economy or elegance. – Jonas Meyer Dec 22 '11 at 6:16 Ah, thanks, missed the obvious! Also answers my question about p^k. – Mike K. Dec 22 '11 at 6:18 @Mike: You're welcome. In case you aren't aware, you may be interested in a framework for thinking about such problems given by modular arithmetic. Here we are working in the ring of congruence classes modulo $6$, with the sample multiplication facts $\overline1^2= \overline1$ and $\overline5^2=\overline 1$. – Jonas Meyer Dec 22 '11 at 6:25
show 1 more comment

HINT $\:$ Generally $\rm\:n\:$ coprime to $\rm\: 6\ \Rightarrow\ n^2 \equiv\: 1\pmod{24}\$ since

$\rm\qquad 3\nmid n\ \ \Rightarrow\ \ mod\ 3\!:\ \ n\ \equiv\ \pm 1\ \Rightarrow\ n^2\ \equiv\ 1$

$\rm\qquad 2\nmid n\ \ \Rightarrow\ \ mod\ 8\!: \ \ n\ \equiv \pm1,\:\pm3\ \Rightarrow\ n^2\ \equiv 1$

Your example is a special case, since primes $> 3$ are coprime to $2$ and $3$ so coprime to $6$.

-