Proof that $ p^2 \equiv 1 \mod{30} \vee p^2 \equiv 19 \mod{30} $ for $p>5$

Question

Proof that $$ p^2 \equiv 1 \mod{30} \vee p^2 \equiv 19 \mod{30} $$ for $p>5$ and $p$ is prime. $\newcommand{\Mod}[1]{\ (\mathrm{mod}\ #1)}$

My try

Let show that $$p^2 - 1 \equiv 0 \Mod{30} \vee p^2 - 1\equiv 18 \Mod{30}$$ Let check $$p^2 -1 = (p-1)(p+1) $$ We know that (for example from here) that this is dividable by $2$ and by $3$ so by $6$ Let consider $5$ cases: $$\exists_k p=5k \rightarrow \mbox{false because p is prime}$$ $$\exists_k p=5k+1 \rightarrow p^2 - 1 = 5k(5k+2) \rightarrow \mbox{ dividable by 6 and by 5 so we have rest 0}$$ $$\exists_k p=5k+2 \rightarrow p^2 - 1 = (5k+1)(5k+3) \rightarrow \mbox{ ??? }$$ $$\exists_k p=5k+3 \rightarrow p^2 - 1 = (5k+2)(5k+4) \rightarrow \mbox{ ??? }$$ $$\exists_k p=5k+4 \rightarrow p^2 - 1 = (5k+3)(5k+5) \rightarrow \mbox{ dividable by 6 and by 5 so we have rest 0}$$

I have stucked with $???$ cases...

Answer 1

To extend your approach:

Let $p=5k+r$ with $r=1,2,-1,-2.$

As you note, when $r=1,-1$ you get $p^2\equiv 1\pmod{5}$ and hence $p^2\equiv 1\pmod{30},$ since you've already shown $p^2\equiv 1\pmod 6.$

In the other cases, you need to deduce additional properties about $k,$ because just $p=5k\pm 2$ doesn't let us deduce it alone.

If $r=\pm 2$ then $0\equiv p^2-1\equiv (r-1-k)(r+1-k)\pmod{6}.$

So when $r=2,$ we need $(1-k)(3-k)$ divisible by $6$ and hence $k$ is odd and $k\equiv 0,1\pmod{3},$ which means $k\equiv 1,3\pmod{6}.$

When $r=-2,$ we need $(1+k)(3+k)$ divisible by $6$, so you need $k$ odd and $k\equiv 0,2\pmod{3}$ which means $k\equiv 3,5\pmod{6}.$

These two cases can be written $k\equiv r\pm 1\pmod{6}$ for $r\in \{-2,2\}.$ Writing $k=6m+r\pm 1$ you get:

$$p=5k+r=30m+5r\pm 5 +r=30m+6r\pm 5,$$ and so:

$$p^2-1 \equiv (6r\pm 5)^2 =36r^2\pm 60r+25=6r^2+ 25=49\equiv 19\pmod{30}$$ sihce $r^2=4.$

---

An easier proof:

Start with $p^2\equiv 1\pmod 6$ if $\gcd(p,6)=1$ and $p^2\equiv \pm 1\pmod{5}$ if $\gcd(p,5)=1.$

Now,

1. Show if $m\equiv 1\pmod{6}$ and $m\equiv 1\pmod{5}$ then $m\equiv 1\pmod{30}.$

2. Show if $m\equiv 1\pmod{6}$ and $m\equiv -1\pmod{5}$ then $m\equiv 19\pmod{30}.$

The first follows since $6\mid m-1$ and $5\mid m-1$ and $\gcd(6,5)=1$ means $30=6\cdot 5\mid m-1.$

The second is is an application of Chinese remainder theorem.

---

You actually can get the stronger result, that $p^2\equiv 1\pmod{24},$ when $\gcd(p,6)=1,$ and hence:

If $p$ is prime and $p>5$ then $$p^2\equiv 1,49\pmod{120}.$$

This is not just true for primes $p>5,$ but for any integer $p$ with $\gcd(p,30)=1.$

Answer 2

$p^2-1$ is divisible by $2$ and $3$ and leaves remainder $0$ or $3$ when divided by $5$

[since if $p\not\equiv0\pmod{5}$ then $p^2\equiv1$ or $4\pmod5$].

In the former case, $p^2-1\equiv0\pmod{30}$; in the latter, $p^2-1\equiv18\pmod {30}.$

Answer 3

Any prime $> 5$ is congruent to $1$ mod $2$, to $1$ or $2$ mod $3$, and to $1, 2, 3$ or $4$ mod $5$. Its square is congruent to $1$ mod $2$, to $1$ mod $3$, and to $1$ or $4$ mod $5$. The numbers that are congruent to $1$ mod $2$, to $1$ mod $3$ and to $1$ mod $5$ are congruent to $1$ mod $30$, while those that are congruent to $1$ mod $2$, to $1$ mod $3$ and to $4$ mod $5$ are congruent to $19$ mod $30$ (see Chinese Remainder Theorem).

Answer 4

$p$ doesn't need to be prime

The set of co-primes to $30,<30$ are $$1,30-1;7,30-7;11,30-11;13,30-13$$

If $p\equiv\pm1\pmod{30},p^2\equiv?$

Check for $p\equiv\pm7,\pm11,\pm13$

Answer 5

$\ 5< p$ prime $\,\Rightarrow\, \begin{align} p&\equiv\pm1\ \ \ \ \ \pmod{\!6}\\ p&\equiv \pm1,\pm2\!\!\!\pmod{\!5}\end{align}$ $\,\Rightarrow\,\begin{align}\color{#0a0}{p^2}&\: \color{#0a0}{\equiv\, 1 \pmod{\!6}}\\ p^2&\equiv \color{#c00}{\pm1}\!\!\!\!\pmod{\!5}\end{align}\!$ $\overset{\rm CRT}\iff p^2\equiv 1,19\pmod{\!30}$

because $\ p^2\!-\!1\bmod 30 = 6\left[\color{#0a0}{\dfrac{p^2\!-\!1}{6}}\bmod 5\right] = 6\left[\dfrac{\color{#c00}{0,3}}{1}\bmod 5\right] = 0,18.\ \ \ \small\rm QED $