Problem of primes

Number Theory Level 4

A prime $q$ divides both $n^2 + 3$ and $n^2 +2n +4$ for some integer $n$ .

The remainder when $n$ is divided by $q$ is $r$ . Find $q + r$ .

19 15 11 13

1 solution

Arpan Mathur
Feb 8, 2017

Since $q | n^2 + 3$ and $q | n^2 + 2n + 4 \Rightarrow q | 2n + 1 \Rightarrow 2n + 1 = k q ...(1)$ , where k is integral.

Also $q | n^2 + 3 \Rightarrow n^2 + 3 = mq ...(2)$ , where m is integral.

Eliminating $n$ in Equations $(1)$ and $(2)$ gives $4mq + 2kq -k^2q^2= 13 \Rightarrow q(4m + 2k -k^2q) = 13 \Rightarrow q |13 \Rightarrow \boxed{q = 13}$ .

Now $(1)$ and $(2)$ may be rewritten as congruences:

$2n \equiv -1 \pmod{13}$ and $n^2 \equiv -3 \pmod{13}$ . Solving both simultaneously yields $n \equiv 6 \pmod{13}$ i.e $\boxed{r = 6}$ .

Thus $\boxed{q + r = 19}$ .

To elaborate on what you're doing in the first half of the solution (and disspelling some of the magic that seems to be happening), essentially you are looking for polynomial combinations of $n^2 + 2n + 4, n^2 + 3$ that will give a linear term. In such a case, using the euclidean algorithm gives us a deterministic process, as opposed to having to "guess" at how to eliminate $n$ . We have

$\begin{array} { l l l l l l } (n^2 + 2n + 4) & - ( n^2 + 3) & = & 2n + 1 \\ 4(n^2 + 3) & - (2n-1)(2n+1) & = & 13 \\ \end{array}$

Hence, $( - 2n+1) ( n^2 + 2n + 4 ) + (2n+3) ( n^2 + 3) = 13$ .

Note: The identity $q ( 4m + 2k - k^2 q) = 13$ in the solution translates into
$4 (n^2 + 3 ) + 2 \left( (n^2 + 2n + 4) - ( n^2 + 3) \right) - \left( (n^2 + 2n + 4) - ( n^2 + 3) \right) ^2 = 13$ ,
When carefully expanded, this does indeed lead to the equation $( - 2n+1) ( n^2 + 2n + 4 ) + (2n+3) ( n^2 + 3) = 13$ .

Calvin Lin Staff - 4 years, 4 months ago

@Calvin Lin Thanks

Arpan Mathur - 4 years, 4 months ago

Problem of primes

1 solution

0 pending reports