# Proof by Contradiction Problem Where do i start

Prove the following: There are no rational number solutions to the equation $x^3 +x+ 1$ = 0, i.e. no solution can be written as a ratio a/b where a, b ∈ N (you can always consider a/b to be reduced to lowest terms). Hint: start your proof as you would start a proof by contradiction, then multiply by $b^3$ to get rid of the denominators. Then consider a case analysis of a and b based on even and odd.

Not sure where to start on this proof by contradiction do i work backwards? Any help would be awesome! Thanks!

-
Example: Suppose $a$ is even and $b$ is odd. Then $a^3+ab^2$ is even, and $b^3$ is odd, which implies that $a^3+ab^2+b^3$ is odd. This is impossible, since $a^3+ab^2+b^3=0$, and $0$ is even. Continue with the other possibilities. –  André Nicolas Mar 16 '12 at 6:32
Is this a homework problem? If it is be sure to include the homework tag. –  Patrick Mar 16 '12 at 6:37

If Bill's answer seems a bit too fancy, just follow the hints. Setting $x = a/b$ and multiplying by $b^3$, your equation becomes $a^3 + a b^2 + b^3 = 0$. There are three cases to consider: $a$ odd and $b$ odd, $a$ odd and $b$ even, $a$ even and $b$ odd. What is $a^3 + a b^2 + b^3$ in each of those cases?

-
So just subtitute to find those cases with actual #'s? –  soniccool Mar 16 '12 at 6:26
By "what is", I don't mean "what actual number", I mean "is it even or odd?" –  Robert Israel Mar 16 '12 at 7:20

Assume there is such a solution $x=\frac{a}{b}$, and plug it into the equation to get a new equation in $a$ and $b$. Then follow the hint you mentioned.

-

Start by assuming that $\rm\:a/b\:$ is a root in lowest terms, then follow the hints. Since $\rm\:a/b\:$ is in lowest terms, $\rm\:a,b\:$ are not both even. Next, considering the remaining parity cases for $\rm\:a,b\:$ leads to the contradiction that $\rm\: a^3 + a\:b^2 + b^3 = 0\:$ is odd, since if $\rm\:a,b\:$ have opposite parity then the sum has two even terms and one odd term, and if $\rm\:a,b\:$ have equal parity then they are both odd, so all three summands are odd, hence so too is their sum. This parity contradiction completes the proof.

If you know a little algebra, below is a generalization from my post here. (e.g. let $\rm\:R = \mathbb Z\:$ below).

PARITY ROOT TEST $\$ Suppose $\rm\:f(x)\:$ is a polynomial with coefficients in a ring $\rm R$ with parity. Then $\rm\:f(x)\:$ has no roots in $\rm R$ if $\rm\:f(x)\:$ has constant coefficient and coefficient sum both being odd. Further, $\rm\:f(x)\:$ has no roots in the fraction field of $\rm R$ when $\rm R$ is a domain such that $\rm\:R/\hat{2}\:\!\cong\mathbb Z/2,\:$ and $\rm\:f\:$ has odd lead coefficient, and $0$ is the only $\rm\:r\in R\:$ divisible by unbounded powers of $\hat 2$.

Proof $\$ The test simply verifies $\rm\ f(0) \equiv f(1) \equiv 1\:\ (mod\ 2),\$ i.e. $\rm\: f(x)\:$ has no roots $\rm\: (mod\ 2)\:.\$ Therefore $\rm\:f(x)\:$ has no roots in $\rm\:R\:.\:$ For the fractional case, by the hypothesis, we may cancel powers of $\hat 2$ from a fraction $\rm\:a/b\:$ till $\rm\:a,b\:$ aren't both even. $\rm\:b\:$ isn't odd, else $\rm\:a/b\equiv a\pmod{2}\:$ would be a root, so $\rm\:b\:$ is even and $\rm\:a\:$ is odd. Now $\rm\:0 = b^n\:f(a/b) = f_n a^n + b\:(\cdots) \equiv 1\pmod{2},\:$ contradiction, since the leading coefficient $\rm\:f_n$ and $\rm\:a\:$ are both odd, and $\rm\:b\:$ is even. $\$ QED

-

The more general case is the Rational roots theorem.
Suppose a/b is a solution to the given equation. $b\neq 0$ and $(a,b)=1$. After multiplying with $b^3$ we have $a^3 + ab^2 + b^3 = 0$ or $a^3 = -ab^2 - b^3$.
If $|b| \neq 1$ and p is its prime factor, we have $p|a^3$ and consequently p|a (prime factorization of a is unique) which mean p divides both a and b, a contradiction.
If |b| = 1, we have $a^3 = -a \pm 1$ which cannot happen since a and $a^3$ always have same parity ( this can be checked directly).

-