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)?
Squares of primes in the sequence 7 + 6k
-
4Looks 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$? – 2011-12-22
2 Answers
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.
-
0@JonasMeyer Thanks for the tip, I have seen some modular arithmetic before. My original question has led me to another which is this: What is the distribution of p^k mod n, and are there interesting n for which this distribution has interesting properties? (Much too vague for another math.SE at the moment, and I'm trying to do more homework this time). – 2011-12-22
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$.