Three years, back and forth #3

Number Theory Level 5

Find the number of positive integral solutions to the following equation for which $x<20000$ .

$\large2015x^3+2018=2021y$

For more try this and this

The answer is 30.

2 solutions

Mark Hennings
May 8, 2018

We need to solve the congruence $2015x^3 \equiv 3 \pmod{2021}$ , which is equivalent to $x^3 \equiv 1010 \pmod{2021}$ , which is in turn equivalent to the simultaneous congruences $x^3 \equiv 21 \pmod{43} \hspace{2cm} x^3 \equiv 23 \pmod{47}$ Testing gives the solution to the congruence $x^3 \equiv 21 \pmod{43}$ as $x \equiv 4,15, 24 \pmod{43}$ , while the congruence $x^3 \equiv 23 \pmod{47}$ has the single solution $x \equiv 38 \pmod{47}$ .

If $x \equiv 4 \pmod{43}$ and $x \equiv 38 \pmod{47}$ , then we can use the Chinese Remainder Theorem to obtain $x \equiv 649 \pmod{2021}$ . If $x \equiv 15 \pmod{43}$ and $x \equiv 38 \pmod{47}$ , then we can similarly obtain $x \equiv 273 \pmod{2021}$ . Finally, if $x \equiv 24 \pmod{43}$ and $x \equiv 38 \pmod{47}$ , we obtain $x \equiv 884 \pmod{2021}$ . Thus the solutions of our original equation are of the form $x \equiv 273\,,\,649\,,\,884 \pmod{2021}$ . There are $\boxed{30}$ such numbers between $1$ and $19999$ .

Sir, how did you break $x^3 \equiv 1010 \pmod{2021}$ into $x^3 \equiv 21 \pmod{43}\text{ and } x^3 \equiv 23 \pmod{47}$ ?

Shreyansh Mukhopadhyay - 3 years, 1 month ago

$2021 = 43 \times 47$ and $1010 \equiv 21 \pmod{43}$ and $1010 \equiv 23 \pmod{47}$ .

Mark Hennings - 3 years, 1 month ago

@Mark Hennings Sir, how did you test the solutions manually?? I tried but only found the solutions 4 and 15 to the first equation and after that, it was practically impossible to solve on paper....Any help??

Aaghaz Mahajan - 3 years, 1 month ago

One method is: Excel

You can do the first by noting that the equation $x^3 \equiv 21 \pmod{43}$ is the same as $x^3 \equiv 64 \equiv 4^3 \pmod{43}$ , and so we need to solve the equation $x^3 - 4^3 \equiv (x - 4)(x^2 + 4x + 16) \equiv (x-4)\big((x+2)^2 + 12\big) \pmod{43}$ so we can break it down to either $x \equiv 4 \pmod{43}$ or each $(x+2)^2 \equiv 31 \pmod{43}$ . At least this means that we are only solving a quadratic equation. Given that you found $15$ , you have one of the roots, and it will then be easy to find the other one.

The other equation can be handled similarly. Since $x^3 \equiv 23 \equiv -9^3 \pmod{47}$ we obtain one root ( $38$ ) and can reduce the rest of the eqation to a quadratic. If you know about quadratic residues and Legendre symbols, you can show that this quadratic has no roots, and hence that $38$ is the only solution modulo $47$ .

Mark Hennings - 3 years, 1 month ago

@Mark Hennings Oh!! Thanks a lot Sir..!! I don't know why the breaking down into quadratics did not strike me!! Thanks a lot!!

Aaghaz Mahajan - 3 years, 1 month ago

I found only the following 9 solutions. Which are the others?

$( 649, 272547893)$ , $( 2670, 18977653858)$ , $( 6712, 301484216378)$ , $( 8357, 581915524353)$ , $(10378,1114422151538)$ , $(10754,1239991857618)$ , $(16441,4430915062373)$ , $(17052,4943501939578)$ , $(18189,5999778340336)$

Janardhanan Sivaramakrishnan - 3 years, 1 month ago

Sir, the solutions are of the form $x \equiv 273\,,\,649\,,\,884 \pmod{2021}$ . Anyways was your approach different from sir Mark Hennings'?

Shreyansh Mukhopadhyay - 3 years, 1 month ago

Kyle Gray
May 9, 2018

This is trivial in python.

solutions = 0
for x in range(1, 20000+1):
    if ((2015 * x**3) + 2018) % 2021 == 0:
        solutions = solutions + 1

print(solutions)

Three years, back and forth #3

The answer is 30.

2 solutions

0 pending reports