A prime number problem from Bulgaria

Let $f(p,q) = p-\lfloor \frac{p}{q} \rfloor q.$ Then $f(p,q)$ is just the remainder upon dividing $p$ by $q.$

It's not hard to see that $p=3,5,7,13$ have the given property and $p=11$ does not (because $f(11,7) = 4$ is not squarefree). From now on, we will assume that $p>13.$

If $q$ divides $p-4$ and $q>4,$ then $f(p,q)=4$ and hence $f(p,q)$ is not squarefree. Since $p-4$ is odd (and larger than 1), this implies that $p-4$ is only divisible by $3$ ; that is, it's a power of $3.$ So write $p=3^k+4$ for some $k \ge 3.$

If $q$ divides $p-8$ and $q>8,$ then $f(p,q)=8$ and hence $f(p,q)$ is not squarefree. Since $p-8$ is odd (and larger than 1), this implies that $p-8=3^k-4$ is only divisible by $3,5,$ or $7.$ But $3$ is impossible, so it's only divisible by $5$ or $7.$

If $q$ divides $p-9$ and $q>9,$ then $f(p,q)=9$ and hence $f(p,q)$ is not squarefree. Since $p-9$ is not divisible by $3$ (and larger than 1), this implies that $p-9=3^k-5$ is only divisible by $2,5,$ or $7.$ But $5$ is impossible, so it's only divisible by $2$ or $7.$

If $q$ divides $p-12$ and $q>12,$ then $f(p,q)=12$ and hence $f(p,q)$ is not squarefree. Since $p-12$ is odd (and larger than 1), this implies that $p-12 = 3^k-8$ is only divisible by $3,5,7,$ or $11.$ But $3$ is impossible, so it's only divisible by $5,7,$ or $11.$

Now, $3^k-5 \equiv 4,6$ mod $8$ for all $k,$ so $3^k-5$ cannot be a power of $2$ (since it's larger than 4). So it's divisible by $7.$ So $3^k-4$ and $3^k-8$ can't be divisible by $7.$ This implies that $3^k-4$ is divisible by $5.$ This implies that $3^k-8$ is not divisible by $5.$

The upshot of the above paragraph is that $3^k-8$ must be divisible by $11.$ (Note that we are using $p>13$ here, because that gives $3^k-8 > 1,$ so it must have at least one positive prime divisor, and $11$ is the only one left.)

But $3^k \equiv 3,9,5,4,1$ mod $11,$ so $3^k-8$ cannot be divisible by $11.$

Hence no $p>13$ has the given property, so the full list is $p=3,5,7,13,$ which sum to $\fbox{28}.$

Just searched first 100 prime numbers using Mathematica

Total@Prime@Select[Range[2,100],And@@Table[SquareFreeQ[Prime@#-Floor[Prime@#/Prime@i]*Prime@i],{i,#-1}]&]

returns 28

The primes that have this property are 3, 5, 7, 13