I guess this is supposed to be "...there does not exist an integer $ a>1$ such that $ a^2 | r$"?

I'm still new to this writing a proof thing, so I'd appreciate it if people could comment on how I could improve, thx

Case 1 seems fine, however: Math4tots wrote: Case 2: p is a prime of the form $ 3^k + 4$. In this case, let us consider $ k \ge 4$. Then $ p - 7^2 = 3^k - 45 = 9(3^{k - 2} - 5)$. Since $ k \ge 4$, the expression is positive, and is divisible by the square of a prime. Trying cases for $ k = 1$ to $ k = 3$, we see that $ 7$ and $ 13$ are also numbers we are looking for. This is not very clear to me. What do you take $ q$ and $ r$ to be in this case? If not the proof itself, at least the exposition seems to be flawed.

This is not a problem too difficult. I will try to make a resolution in the shortest time(by the busy work )

math10 may have given up, so here's my solution. We prove that if $ p > 13$ is prime, there is a prime $ q < p$ such that the least residue of $ p$ modulo $ q$ is not square-free, which is the property described in the problem. In fact, we prove a stronger statement: if $ p>13$ is odd (not necessarily prime), there is a prime $ q$ such that the least residue of $ p$ modulo $ q$ is either $ 4$, $ 8$ or $ 9$. Suppose that some odd $ p>13$ is a counterexample: there's no prime $ q < p$ for which the remainder upon dividing $ p$ by $ q$ belongs to $ \{4,8,9\}$. If there is a prime $ q > 3$ diving $ p-4$, then $ 4$ is the least residue of $ p$ modulo $ q$, which contradicts our assumption on $ p$. Since $ p$ is odd, $ p-4$ is also not divisible by $ 2$, so the only prime divisor of $ p-4$ must be $ 3$. In other words, $ p-4 = 3^k$ for some natural number $ k$. Consider now $ p-8$. If it has any prime factor greater than $ 8$, we once again contradict our assumption on $ p$. Thus we may assume that all of its prime factors belong to $ \{2,3,5,7\}$. But $ 2$ is impossible since $ p-8$ is odd, and $ 3$ is impossible since $ p-4$ is divisible by $ 3$. Thus $ p-8$ is divisible only by $ 5$, $ 7$ or both. Next consider $ p-9$. For the same reason as above, it too can only have prime factors among $ \{2,3,5,7\}$. Since $ p-4$ is divisible by $ 3$ and not by $ 5$, $ p-9$ is divisible by neither $ 3$ nor $ 5$. It may or may not be divisible by $ 7$, but we claim that in either case our previous friend $ p-8$ cannot be divisible by $ 7$. Here's why: If $ p-9$ is divisible by $ 7$, then $ p-8$ certainly isn't. If $ p-9$ is not divisible by $ 7$, then it must be a power of $ 2$ (since no other prime factors are available). But powers of $ 2$ can only leave remainders of $ 1, 2, 4$ upon division by $ 7$, so $ p-8$ which is one greater than a power of $ 2$ cannot be divisible by $ 7$. Recall that the only possible prime factors of $ p-8$ were $ 5$ and $ 7$, and we just ruled out $ 7$. We may therefore conclude that $ p-8$ is a power of $ 5$: $ p-8 = 5^m$. Comparing this with $ p-4 = 3^k$ we obtain: (*) $ 5^m + 4 = 3^k$ We conclude the proof by showing that (*) only has the trivial solution $ 5+4 = 3^2$, which corresponds to $ p=13$. Reducing mod $ 4$ we see that $ k$ must be even, so $ k = 2t$ for some $ t$. Now $ 5^m = 3^{2t} - 4 = (3^t-2)(3^t+2)$. But these factors cannot both be divisible by $ 5$ (they differ by $ 4$), so the only way their product can be a power of $ 5$ is if one of them is $ 1$ and the other is a power of $ 5$. This forces $ t=1$, $ k=2$ as required. QED

randomgraph wrote: Case 1 seems fine, however: Math4tots wrote: Case 2: p is a prime of the form $ 3^k + 4$. In this case, let us consider $ k \ge 4$. Then $ p - 7^2 = 3^k - 45 = 9(3^{k - 2} - 5)$. Since $ k \ge 4$, the expression is positive, and is divisible by the square of a prime. Trying cases for $ k = 1$ to $ k = 3$, we see that $ 7$ and $ 13$ are also numbers we are looking for. This is not very clear to me. What do you take $ q$ and $ r$ to be in this case? If not the proof itself, at least the exposition seems to be flawed. This finish is somewhat similar. Take $r=5^2$, $q =$ a prime that divides $3^{k - 1} - 7 = \frac{p-5^2}{3}$ that is greater than $5$. Since $k \geq 4$ the number $3^{k-1}-7 >1$ and $3 \not |5$, so it is not a power of 3, and if $5|3^{k-1}-7$ then $5|p$, contradiction. Thus if $q$ does not exist, then $3^{k-1}-7$ is a power of 2. However $3^{k-1}-7 \equiv 4,2 (mod 8),$ so $3^{k-1}-7 \leq 4 \implies k<4$, contradiction. Now finish as in the quote by considering cases $k\in [1,3]\cup \mathbb{N}$.