2

Wrote a program to list all primes $n$ below $1,000,000$ and noticed they never satisfied (except $n=5$)

$\frac {n-1}2 \equiv 2 \pmod{10}$

or

$\frac {n-1}2 \equiv 7 \pmod{10}$

Is that true for all primes? Thanks.

#include <stdio.h>
#include <stdint.h>

int isPrimeNumber(int number)
{
    int iLoop = 0;
    int iPrimeFlag = 1;


if (number &lt;= 1)
{
    iPrimeFlag = 0;
}
else
{
    for (iLoop = 2; iLoop &lt; number; iLoop++)
    {
        if ((number % iLoop) == 0)
        {
            iPrimeFlag = 0;
            break;
        }
    }
}
return iPrimeFlag;



}


int main(int argc, char* argv)
{
    uint64_t n, i, m;


for (n = 2; n &lt; 1000000; n++)
{
    if (isPrimeNumber(n) == 1)
    {
        i = (n - 1) / 2;
        m = i % 10;

        if (m == 2 || m == 7)
        {                    
            printf(&quot;n=%llu i=%llu\n&quot;, n, i);
        }
    }
}

return 0;



}
vengy
  • 1,903

2 Answers2

1

Your two congruences simplify to $n\equiv5\bmod10$, which is obviously not true for any prime except $5$.

Parcly Taxel
  • 103,344
  • Test n=15 in the first congruence and n=5 in the second. Right idea, wrong execution. – Mike Jan 07 '21 at 05:09
1

Just do it. Equivalence $\pmod n$ distributes over multiplication, addition and subtraction (but not division) so

$\frac {n-1}2 \equiv 2 \pmod{10}\implies$

$2(\frac {n-1}2) + \equiv 2\cdot 2 + 1 \pmod {10}\implies$

$n \equiv 5 \pmod {10}$

And the definition of $a\equiv b\pmod n$ is $n\mid a-b$ so

$10 \mid n-5$.

Now $10 = 2\cdot 5$ so that means $2|n-5$ and $5|n-5$.

And if $a|b$ then $a|b \pm ka$ for any multiple $ka$ of $a$.

so $5|(n-5) \implies 5|(n-5)+ 5\implies 5|n$.

But if $n$ is prime that's only possible if $n = 5$.

Can you do the other one.

fleablood
  • 124,253