Solutions to $x^4+x^3-x-1\equiv0\bmod15$

Question

$$x^4+x^3-x-1\equiv0\bmod15$$ In attempting to solve this equation I thought of using a congruence mod $p$ in order to show that no solutions mod $p$ implies no solutions to the equality. But I have come to the conclusion that this method is not going to work because if 1 is subbed into the equation it gives 0 no matter the $p$.

From my intuition I feel like there is a solution because it gives 0 when 1 is subbed in. But I am unsure which tools I could use to help me solve it.

Answer 1

Hint

The given equation can be reduced as $$(x^3-1)(x+1)\equiv 0\pmod {15}$$ Hence $$x\equiv 1 \pmod {15}$$ or $$ x\equiv 14 \pmod {15} $$ or $$ x^2+x\equiv 14 \pmod {15} $$

Edit 1:

As by the explanation given by Fleablood, we have by Chinese Remainder Theorem $$x\equiv 1,2\pmod 3$$

And

$$x\equiv-1,1\pmod 5$$

Hence giving us

$$x\equiv 1,4,11,14 \pmod {15}$$

Answer 2

If worse comes to worse there are only $15$ values to check but lets start by trying to factor $x^4 + x^3-x-1 = x^3(x + 1) - (x+1) = (x^3-1)(x+1)$.

So $(x^3-1)(x+1) \equiv 0 \mod 15$.

So either $x^3-1$ of $x+1$ are multiples of $15$ or one of $x^3-1$ or $x+1$ is a multiple of $3$ and the other is a multiple of $5$.

Case 1: $x^3 -1\equiv 0 \mod 15$

$x^3 \equiv 1 \mod 15$. If $\gcd(x,15)\ne 1$ this is impossible and be Fermat's Little theorem $x^{\phi(15)} = x^8\equiv 1 \mod 15$. So the order, the smallest power $k$ of $x$ so that $x^k \equiv 1$, must by so that $k|8$ and $k|3$. So $k=1$ and $x\equiv 1 \mod 15$.

Case 2: $x+1\equiv 0 \mod 15$ so $x \equiv -1 \mod 15$

Case 3: $x^3 - 1\equiv 0 \mod 5$ and $x+1\equiv 0 \mod 3$.

Then $x^3 \equiv 1 \mod 5$ and that meas by similar but simpler argument above that $x \equiv 1 \mod 5$ and $x\equiv -1 \mod 3$ so $x \equiv 11 \mod 15$.

Case 4: $x^3 - 1\equiv 0 \mod 3$ and $x+1 \equiv 0 \mod 5$.

$x^3\equiv 1\mod 3$ so $x\equiv 1 \mod 3$ (ditto above). And $x \equiv -1 \mod 5$ so $x \equiv 4 \mod 15$.

So $x \equiv 1,4,11, 14 \mod 15$ are all the solutions.

....

It's also possible to note $ac\equiv bc \mod n\iff a\equiv b \mod \frac n{\gcd(n,c)}$

So

$x^3(x+1) \equiv (x+1) \mod 15$

$x^3 \equiv 1 \mod \frac {15}{\gcd(15,x+1)}$

which yields the some results for the same reason but might be shorter.

=====

Argh! SOOO much easier to use the chinese remainder theorem from the start.

If $x\equiv 0 \mod 5$ or $x\equiv 0 \mod 3$ then it cant be a solution. (Because the result would be $\equiv -1 \mod 3$ or $\equiv -1 \mod 5$ which can't be $\equiv 0 \mod 15$). So as $3$ and $5$ are prime, $x$ is relatively prime to $3$ and to $5$.

By chinese remainder theorem we have

$x^4 + x^3 - x -1 \equiv 1 + x-x-1 \equiv 0 \mod 3$ so $x$ can be ... anything that is relatively prime to $3$; Either $\equiv 1,2 \mod 3$.

$x^4 + x^3 - x -1 \equiv 1 + x^3 -x -1\equiv x^3 - x\equiv x(x^2-1)\equiv x(x+1)(x-1) \equiv 0 \mod 5$ so as $x \not \equiv 0 \mod 5$ and $5$ is prime so modulo $5$ there are no zero-divisors, we have either $x+1$ or $x-1$ is $\equiv 0 \mod 5$. so $x \equiv \pm 1 \mod 5$.

So $x \equiv 1,2\mod3$ and $x\equiv \pm 1\mod 5$.

Each of those four combinations gives a unique solution modulo $15$.

So $x \equiv 1,11,4,14 \mod 15$.

Answer 3

You begin with factoring the polynomial* $$x^4+x^3-x-1=(x+1)(x^3-1).$$ Next, you use the Chinese remainder theorem: $$\mathbf Z/15\mathbf Z\simeq \mathbf Z/3\mathbf Z\times\mathbf Z/5\mathbf Z $$ which makes the equation come down to two congruence equations

• Modulo $3$, Fermat $(x^3\equiv x\mod 3$) shows the only solutions are $\pm$1.
• Modulo $5$, the equation is equivalent to $x\equiv -1$ or $x^3\equiv 1\mod 3$. But since $x^4\equiv 1\mod 5$ if $x\not\equiv 0$, the latter congruence means $x^{-1}\equiv 1$, which is the same as $x\equiv 1\mod4$.

So the solutions in the product are the fours pairs $$\bigl\{\pm1\bmod 3,\pm1\bmod 5\bigr\}$$ which, since $2\cdot 3-5=1$, correspond modulo $15$ to the values $$\bigl\{\pm2\cdot 3\pm 5\bigr\}=\bigl\{1, 11\equiv -4, -11\equiv 4,-1\equiv 14\bigr\}.$$