Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)?

share|improve this question
4  
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
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
+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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.