$p\mid q^{2}-4\Rightarrow q^{2}\equiv4\mod{p}\Rightarrow q\equiv\pm2\mod{p}$ $q\mid p^{2}-1\Rightarrow p^{2}\equiv1\mod{q}\Rightarrow p\equiv\pm1\mod{q}$ Note from $p\equiv\pm1\mod{q}$ that $p\neq q$. Case 1: $p<q$ If $p\equiv 1\mod{q}$ then we have $p=1$ which is not prime. If $p\equiv -1\mod{q}$ then $p=q-1$ so as $p,q$ are primes we have $p=2,q=3$ which is not a solution as $2\nmid 3^{2}-4$ Case 2: $p>q$ If $q\equiv 2\mod{p}$ then we have $q=2$ so $p\mid 0, 2\mid p^{2}-1$ which holds for all odd primes $p$. If $q\equiv -2\mod{p}$ then we have $q=p-2$. From $q\mid p^{2}-1$ we have $q\mid (q+2)^{2}-1=q^{2}+4q+3\Rightarrow q\mid3\Rightarrow q=3\Rightarrow p=5$ which is a solution. Thus $(p,q)=(5,3);(P,2)$ for $P$ an odd prime are the only solutions.

Nice solution.

3 is an odd prime, and so "$(P,2)$ for $P$ an odd prime" accounts for $(3,2)$.

Hi djmathman! If $q$ is even then $q=2$ so $(p,q)=(p,2)$ , $p\neq2$. If $p$ even then $p=2$ so no solutions. If now $p$ odd (and $q$ odd ) then $p|q-2$ or $p|q+2$ so $\boxed{p\leq{q+2}}$ (1) Also $q|p-1$ or $q|p+1$ but $p$ odd so $q|\dfrac{p-1}{2}$ or $q|\dfrac{p+1}{2}$ so $\boxed{q\leq{\dfrac{p+1}{2}}}$ (2) From $(1),(2)$ $p\leq5$ , $q\leq3$ so finally $(p,q)=(p,2)$ with $p\neq3$ and $(5,3)$

(3,2) is also the solution so why p is not equals to 3.

MIT1999J wrote: (3,2) is also the solution so why p is not equals to 3. Obvious typo.The correct is $p\neq2$ as i wrote in the beginning of solution.Thanks.

I Got a solution.. Clearly $q\neq2$ as then $q^2-4=0$. If $p=2$ then $q|p^2 - 1$. This implies $q|3$ so $q=3$ is a solution..Thus $(p.q)=(2,3)$.. Suppose that $p$ ≤ $q$. Since $q$ divides $(p - 1)(p + 1)$ and $q > p - 1$ it follows that $q$ divides $p + 1$ and hence $q = p + 1$. Therefore $p = 2$ and $q = 3$. On the other hand, if $p > q$ then $p$ divides $(q - 2)(q + 2)$ implies that $p$ divides $q + 2$ or $q - 2 = 0$. This gives either$ p = q + 2$ or $q = 2$. In the former case it follows that that$q$ divides $(q+2)^2 -1$, so $q $divides $3$. This gives the solutions $p > 2, q = 2$ and $(p, q) = (5, 3)$.

Why not think simpler and avoid calling congruences everytime? Observe.. Assume both $p$ and $q$ to be odd. $p\mid (q+2)(q-2)$ and $q\mid (p+1)(p-1)$ $\implies p\leq (q+2)$ and $q\leq (p+1)$ Therefore, $q$ must lie between $(p-2)$ and $(p+1)$ (both inclusive).. But, as we have already assumed that $p$ and $q$ are both odd, therefore, the number immediate to a prime number cannot be prime. This forces us to conclude that $q=p-2$ is the only possible choice. Therefore, now we are only bothered about all those prime numbers who differ by $2$. But the only solution to this is $(p,q)=(5,3)$. Why? Hehe, simple enough.. $\because q\mid (p+1)(p-1)$ and $q\neq (p+1)$ or $(p-1)$. $\therefore$ atleast $2q\leq(p+1)$. This holds true for the first pair, $(5,3)$.. But as we move on to successive such pairs, the magnitude increases and this can never hold true... example for, $(p,q)=$ $(7,5)$ , $(13,11)$ and so on..... Hence, if $p$ and $q$ are both odd, the only solution is $(p,q)=(5,3)$. Now, if we allow $p$ or $q$ to be $2$, then it's trivial to observe that $q=2$ is a solution, for which $p\mid 0$ and it is satisfied for any odd prime $p$. And $p\neq 2$ $\because$ this forces $q$ to become $3$, but $2\nmid (3-2)(3+ 2)$.. So, the only possible solutions to this problem is $(p,q)=(5,3)$ or $(\beta,2)$, where $\beta$ is any odd prime number.. Simple ! $\square$

My soln $q$ | $p^2-1$ $\implies$ $q$|$p-1$ or $q$|$p+1$ $C1:$ $q$|$p-1$ So $q \leq p-1$ BY $p$| $q^2-4$ We should be having $p$| $q-2$ or $p$|$q+2$ So either $p \leq q-2$ $p \leq q+2$, If first one is true adding it with first inequality we get $p+q \leq p+q-3$ which is not true! So $p|q+2$, By our first divisiblity we know $q|p-1$ so $p = qk+1$ for some k belongs to natural no So by our second divisibility $qk+1|q+2$ So $qk+1 \leq q+2$ so k must be 1 but that means $q+1 | 1$ which is absurd !! So no solns here $C2:$ $q|p+1$ Like previous case, following the same argument we should get $p | q+2$, so $p = qk-1$ for some k in naturals So $qk-1|q+2$ so $qk-1 \leq q+2$ so $q(k-1) \leq 3$ so either $$k =1$$or $$q=3,2 ,k=2 $$, If $k=1$ then $q-1|q+2$ \implies $q-1|3$ so We get soln $(p,q)= (P,2)$ where P is an odd prime If $q=3,k=2$ so $p|5$ so $p=5$, Hence we get soln $(p,q)= (5,3)$ If $q=2,k=2$ So $p|4$ so we get no solns here! Hence $$(p,q)=(5,3);(P,2)$$For $P$ = odd prime are only solns

p | q²-4 p|(q+2)(q-2) q | p²-1 q| (p+1)(p-1) Case :1 p | q-2, then q | p-1 p is prime , therefore p-1 is always even, except p=2 So, q=2 P be the no.of odd prime number So, one set is(P,2) where P>2 Case :2 p | q+2, q | p+1 so, -2≤ q-p≤1 Since , q and p are integers q-p=-2,-1,1, q-p≠ 0, then p =1 , not prime If q-p=-1 q+1=p so, q| q+2 p|q+2 so, p|q , not possible as both are primes and cannot be equal q-p=1 q=p+1 Then p|2, so p=2, q=3 But p does not divide q²-4 So, q -p=-2 p=q+2 q| q+3 So, q|3, q=3 p=5 So, the solution set is (p,q)= (5,3);(P,2) where P>2