1
$\begingroup$

I was reading some properties on prime numbers in a book and I’ve found this problem. Using Modular Arithmetic isn’t allowed

Using the division algorithm I have found:

$p \in \{5m+1, 5m+2, 5m+3, 5m+4\}$

I’ve tried to plug those values of $p$ to :$\frac{p^{2}\pm1}{10}$, but I didn’t get an integer.

Thank you for your help

$\endgroup$
5
  • $\begingroup$ Hint: an odd prime $p$ different than $5$ is always congruent to $1,3,7$ or $9$ modulo $10$. What happens to those numbers if you look at $p^2\pm1$? $\endgroup$
    – leoli1
    Jan 25, 2021 at 21:13
  • $\begingroup$ @leoli sorry i didn’t mentioned that modular arithmetic isn’t allowed in this problem $\endgroup$
    – PNT
    Jan 25, 2021 at 21:15
  • $\begingroup$ In that case we can go trough the different possibilities $p=5m+1,5m+2,5m+3,5m+4$ and show that $p^2$ is always of the form $5k+1$ or $5k-1$. $\endgroup$
    – leoli1
    Jan 25, 2021 at 21:18
  • 1
    $\begingroup$ You don't need modular artihmetic. Just take the statement from @leoli1 If your prime is odd and not 5, then the last digit must be 1,3,7 or 9. Then, it is always the case that your primer number will be something like $10k+1,10k+3,10k+7$ or $10k+9$. Compute the square of those numbers and you're done $\endgroup$
    – FormerMath
    Jan 25, 2021 at 21:20
  • $\begingroup$ Alternatively you can show separately that BOTH $p^2+1$ and $p^2-1$ are even, and ONE OF THEM is divisible by five. $\endgroup$ Jan 25, 2021 at 21:26

3 Answers 3

4
$\begingroup$

$p$ is odd so $p^{2}$ is odd so $p^{2}\pm 1$ is even. That takes care of the factor of 2. Now we just need the factor of 5. It will be a little tedious since you disallow modular arithmetic but here it goes.

If p=5m+a then

$$p^{2}=25m^{2}+5am+a^2$$

So for $a=1,2,3,4$

$$p^{2}=25m^{2}+5m+1$$

$$p^{2}=25m^{2}+10m+4$$

$$p^{2}=25m^{2}+15m+9$$

$$p^{2}=25m^{2}+20m+16$$

Respectively.

$25m^{2}+20m+16 -1 = 25m^{2}+20m+15$ is clearly divisible by 5.

$25m^{2}+15m+9 + 1 = 25m^{2}+15m+10$ is clearly divisible by 5.

$25m^{2}+10m+4 +1 = 25m^{2}+15m+5$ is clearly divisible by 5.

$25m^{2}+5m+1 -1 = 25m^{2}+5m$ is clearly divisible by 5.

$\endgroup$
2
  • $\begingroup$ I’ve said divisible by 10 not 5 $\endgroup$
    – PNT
    Jan 25, 2021 at 21:57
  • $\begingroup$ If it is divisible by 5 and divisible by 2, it is divisible by 10. $\endgroup$ Jan 25, 2021 at 22:06
1
$\begingroup$

Why on earth would modular arithmetic not be allowed. As I am of the theory all arithmetic is modular arithmetic that may be hard.

But as $p$ is an odd prime $p^2 -1$ and $p^2 +1$ are both even and $2|p^2 \pm 1$ so it is sufficient to show that $5|p^2 -1$ or $5|p^2 + 1$. .... Oh, wait, that was modular arithmetic! Well, too bad.

Now $p$ is odd so $p=2k-1$ for some integer $k$ so $p^2\pm 1 = 4k^2 - 4k+1 \pm 1 =\begin{cases}4k^2 - 4k = &5k^2 - 5k -k^2 + k = &5(k^2-k) -k(k-1)\\4k^2+4k+2 = &5k^2 - 5k - k^2 + k +2=&5(k^2-k) -(k+1)(k-2)\end{cases}$.

Now $k-2,k-1,k,k+1,k+2$ are five consecutive numbers so one of them is divisible by $5$. (Oh wait... that was modular arithmetic!... Oh, well.) If the one divisible by $5$ is $k$ or $k-1$ then $p^2 -1 = 4k^2 -4k = 5(k^2-k) -k(k-1)$ is divisible by $5$

If $k+1$ or $k-2$ is divisible by $5$ then $p^2+1 = 4k^2 -4k + 2 = 5(k^2-k) -(k+1)(k-2)$ is divisible by $5$.

And if $k+2$ is divisible by $5$, then there is an integer $m$ so that $5m = k+2$ so $p = 2k -1=2(5m-2)-1=10m-5 = 5(2m-1)$. But that means $p$ is not a prime other than $5$. So this is impossible. $k+2$ is not divisible by $5$ and one of the other four cases must be true.

.....

But that used modular arithmetic.

$\endgroup$
1
  • $\begingroup$ The book said don’t use it because it wants you to use the properties that it has shown to you $\endgroup$
    – PNT
    Jan 25, 2021 at 23:04
0
$\begingroup$

If $p$ is odd and different from 5, then $p=3$ or $p=7$ or $p=9$ or $p=10k+1$ or $p=10k+3$ or $p=10k+5$ or $p=10k+7$, $k\geq 1$. Suppose that $10$ does NOT divide $p^2-1$ nor $p^2+1$.

Then $10$ does not divide the product: $(p^2-1)(p^2+1)$.

You can verify easily this is not true for 3, 7 and 9. Then you can substitute $p=10k+1$ or $p=10k+3$ $p=10k+5$ or $p=10k+7$ for $k\geq1$ to verify this is not true as well and reach an contradiction.

The conclusion is that $10$ must divide $p^2-1$ or $p^2+1$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .