{x^2 + Ax + B} and {2x^2 + 2x + C} do not intersect

orl

Let $\mathbb{Z}$ denote the set of all integers. Prove that for any integers $A$ and $B,$ one can find an integer $C$ for which $M_1 = \{x^2 + Ax + B : x \in \mathbb{Z}\}$ and $M_2 = {2x^2 + 2x + C : x \in \mathbb{Z}}$ do not intersect.

**Posted:** Sun Aug 10, 2008 8:56 am

_________________
Math is like love. A simple idea but it can get complicated.

t0rajir0u

Write

$x^2 + Ax + B = 2y^2 + 2y + C \Leftrightarrow$
$4x^2 + 4Ax + B = (2x + A)^2 + (B - A^2) = 2(2y + 1)^2 - 2 + 4C \Leftrightarrow$
$(2x + A)^2 - 2(2y + 1)^2 = 2(2C - 1) + A^2 - B$ .

Lemma: No integer of the form $a^2 - 2b^2$ is congruent to $3 \bmod 9$ .

Proof: Suppose that $a^2 - 2b^2 \equiv 3 \bmod 9$ . Clearly $a, b$ are not both divisible by $3$ . If one of $a, b$ was divisible by $3$ , then the other would also have to be, so neither is. Then $a^2 \equiv 2b^2 \bmod 3 \Leftrightarrow \left( \frac {a}{b} \right)^2 \equiv 2 \bmod 3$ , but $2$ is not a quadratic residue $\bmod 3$ ; contradiction.

Since $C$ allows us to increase or decrease the value of the RHS by $4$ and $4$ is invertible $\bmod 9$ , it follows that for any $A, B$ we can find $C$ so that $2(2C - 1) + A^2 - B \equiv 3 \bmod 9$ .

**Posted:** Sun Aug 10, 2008 9:32 pm

_________________
Annoying Precision (http://qchu.wordpress.com/)

ali666

another solution:
note that $2x^2 + 2x$ is divisible by $4$ for all $x$ .
let: $N_1=$ the set $M_1$ mod 4.
therefore:
$N_1 = \{B,A + B + 1,2A + B,3A + B + 1\} \mod 4$
if $A$ is odd,then all elements of $N_1$ have the same parity,therefore $N_1$ is not complete residue system mod 4.
and if $A$ is even then obviously $B\equiv2A + B \mod 4$ therefore $N_1$ is not complete residue system mod 4.
since $N_1$ is not complete residue system mod 4 and $4|2x^2 + 2x$ obviously there exist $C$ such that $M_1$ and $M_2$ do not intersect.

**Posted:** Mon Aug 11, 2008 8:54 am

The QuattoMaster 6000

**Posted:** Thu Sep 25, 2008 4:52 pm

ali666

**Posted:** Fri Nov 21, 2008 7:58 am

dgreenb801

Why is every solution keeping b? Can't we just assume b is 0 since we could adjust c to make up for it?

**Posted:** Tue Mar 03, 2009 7:52 pm

boxedexe

The problem states that for any $A,B$ ..., i.e., given fixed $A,B$ ...

**Posted:** Tue Mar 03, 2009 9:16 pm

dgreenb801

Right, but even if b is fixed we could choose an appropriate c to make up for it. For example, if when b=0 we would choose c=3, then when b=4 we would choose c=7, right?

**Posted:** Wed Mar 04, 2009 5:14 am

ZetaX

ANd why should this specific $C$ work¿

**Posted:** Wed Mar 04, 2009 11:04 am

_________________
The one and only place to get next year's IMO problems already now!

t0rajir0u

dgreenb801 is saying that $\{ x^2 + Ax + B \}$ and $\{ 2x^2 + 2x + C \}$ intersect if and only if $\{ x^2 + Ax \}$ and $\{ 2x^2 + 2x + (C - B) \}$ intersect, which is true but does not significantly shorten the solution (as far as I can see).

**Posted:** Wed Mar 04, 2009 11:16 am

_________________
Annoying Precision (http://qchu.wordpress.com/)