If $(p^2-1)/8$ is an odd number and $p$ is prime odd number what is $p\pmod8$?

Question

So we know $p^2-1$ is divisible by 8, so $p^2 =1\pmod 8$ but this isn't nothing new because this is true for every odd number p. But how to use the fact that $(p^2-1)/8$ is an odd number ? I started with congruence $(p^2-1)/8 = 1\pmod 2 $and then $p^2-1= 8 \pmod {16}$ and because 8|16 I get $p^2-1= 8 \pmod 8=0 \pmod 8$ so $p^2=1 \pmod 8$ and I am at the beginning again...

Answer 1

Let $p=2q+1$

$$\dfrac{p^2-1}8=\dfrac{q(q+1)}2$$ which is odd

if $\dfrac q2$ is odd i.e., $\dfrac q2=2r+1\implies p=2(4r+2)+1\equiv5\pmod8$

or if $\dfrac{q+1}2$ is odd i.e., $\dfrac{q+1}2=2r+1, p=?$

Answer 2

Write $p= 8k+r$ where $r\in\{1,3,5,7\}$ and $$p^2-1 = 8(2l+1)$$

then $$64k^2+16kr+r^2 -1 = 16l+8\implies 16\mid r^2-9$$

• If $r=1$ we get $16\mid -8$, not true,

• If $r=3$ we get $16\mid 0$, true,

• If $r=5$ we get $16\mid 16$, true,

• If $r=7$ we get $16\mid 54$, not true.

So $p=8k\pm 3$. This values for $r$ are achivable, since $p=3$ and $p=5$ are such prime numbers.

Answer 3

$$p^2-1 ≡ 0 \ mod (8)$$

$$p^2-1≡0 \mod (3)$$

⇒ $$p^2-1 = 24 k$$ ⇒ $$p^2=24 k+1=25, 49, 121, . . .$$

$p=±5$: $(25-1)/8=3$; $5≡ 3\mod (8)$

$p=± 7$: $(49-1)/8=6$; not true

$p= ± 11$ : $(121-1)/8=15$; true, $±11≡ ±3 \mod (8)$

So :$ p≡±3\ mod (8)$

Answer 4

You were on the right track by coming to the conclusion that $p^2-1 \equiv 8 \pmod{16}$. I don't know why you went back to the weaker formulation $p^2-1 \equiv 8 \pmod{8}$. I assume that's because you only want to know about $p$ mod $8$. But that, as you found out, is omitting information, namely that not only $\frac{p^2-1}8$ is an integer, but that it is odd!

So, to solve $p^2 \equiv 9 \pmod{16}$, you can easily check each potential remainder class of $p$ mod $16$. To reduce the manual labor, we know that $p$ is odd. Sine $16$ is even, that means $p$ can only be in an odd remainder class. Also, since $(-x)^2 \equiv x^2 \pmod m$ generally, you need to only test remainder classes up to $8$.

That leaves to check $p \equiv 1,3,5 \text{ or } 7 \pmod {16}$, and only $p \equiv 3 \pmod {16}$ and $p \equiv 5 \pmod {16}$ fullfill that. Let's not forget about the "$-x$" classes that we did not test, so we findt that $p^2 \equiv 9 \mod {16}$ is equivalent to $p \equiv 3,5,11 \text{ or } 13 \pmod {16}$.

This can be simplified to $p \equiv 3\text{ or } 5 \pmod {8}$. As Auqu wrote, check that there actually are prime numbers in those remainder classes, and you have the solution.