Prime numbers $p,q \in \Bbb P$ are such that $q\mid p^2+1$ and $p\mid q^2-1$.

Question

Prime numbers $p,q \in \Bbb P$ are such that $q\mid p^2+1$ and $p\mid q^2-1$. Prove that number $p+q+1$ is composite.

If $p+q+1$ is composite, then $p+q$ is also composite because it's even. Have no idea where to start to. Tried to sum, multiply these two fractions $\frac{p^2+1}{q},\frac{q^2-1}{p}$ but didn't get anything useful at all.

Answer 1

Since $p\mid (q-1)(q+1)$ we have $p\mid q-1$ or $p\mid q+1$.

a) If $p\mid q+1$ then $q+1 = kp$ where $k$ is positive integer so $p+q+1= (k+1)p$ is composite.

b) If $p\mid q-1$ then $p\leq q-1$ and $$pq\mid (q-1)(p^2+1) = p^2q-p^2+q-1\implies pq \mid p^2+1-q$$

• If $p^2+1>q$ we get $$pq\leq p^2+1-q\implies q\leq {p^2+1\over p+1} <p$$ So we have $q<p<q$ a contradiction.
• If $p^2+1=q$ then $p$ or $q$ is even. Clearly $q$ is not $2$ so $p=2$ and $q=5$. In this case we get $p+q+1=8$.

Answer 2

Since $p$ is prime and $p \mid q^2 - 1 = (q-1)(q+1)$ one has that either $p\mid q - 1$ or $p \mid q + 1$. In the latter case $p + q + 1$ is the sum of two multiples of $p$ and thus is itself a multiple of $p$ that is greater than $p$, and hence is composite.

Moving to the case that $p \mid q - 1$, we first observe that we must have $q = kp + 1$ for some positive integer $k = \lfloor q/p \rfloor$. So in particular $q > p$. The fact that $q \mid p^2 + 1$ means that $p^2 + 1$ is a multiple of $q$, so that $p^2 + 1 - q = p(p -k)$ is a multiple of $q$. Since $q$ and $p$ are distinct primes, we get that that $q \mid p - k = p - \lfloor q/p \rfloor$. However, $|p - \lfloor q/p \rfloor| < \max(p, \lfloor q/p \rfloor) < q$.

So for $p - \lfloor q/p \rfloor$ to be multiple of $q$ we must have $p - \lfloor q/p \rfloor = 0$, or $p =\lfloor q/p \rfloor = k$. So $q = p^2 + 1$ here. The only way this can happen is for one of $p$ and $q$ to be even, so we have $p = 2$ and $q = 5$ which satisfies the conditions and $p + q + 1$ is composite.