1

I have a problem I want to solve, but I could not figure out how to approach it. And since I do not have formal maths training, I am not very familiar with the terminology so it is possible I may not know the correct keywords for search.

Below are a couple sample equations, which I want to find a way to solve them efficiently, when the numbers are big. So, no trial and error:

$$ k^2 + k + 5 \equiv 0 \, (mod \,\, 13-k) $$

Solution for this is k=2

$$ k^2 + 3028 \equiv 0 \, (mod \,\, 9011-k) $$

And solution for this is k=864

So the question is, how can I solve similar equations with a lot bigger coefficients without trial-error.

Thank you

EDIT: These equations also have negative solutions (k=-4 for the first one and k=-956 for the second one)

UPDATE:

As far as I see from the answers, the solution comes to factoring, which does not have an efficient solution when you have big numbers (more than hundreds of digits) as coefficients.

Thank you for your time and answers. Now I at least know this is really a difficult problem.

xycf7
  • 131
  • do you know how to rewrite them as non modular arithmetic ? that may help. –  Sep 06 '17 at 01:27
  • From the answers I see it looks like you have to factor the quadratic polynomial after inserting $k=$ whatever you are subtracting $k$ from. Does that qualify as sufficiently free from trial and error? And is there an alternative? – Oscar Lanzi Sep 06 '17 at 02:19
  • @OscarLanzi when the numbers are really big, factoring becomes infeasible. And it seems I am out of luck to find a simpler answer. Thank you. – xycf7 Sep 06 '17 at 06:04

2 Answers2

3

$$ k^2 + 3028 = (9011 - k)t, $$ $$ k^2 + 3028 = 9011t - kt, $$ $$ k^2 + kt - 9011 t + 3028 = 0. $$ The degree two stuff factors as $k(k+t)$ so those are your two linear expressions, $k$ and $k+t.$ We try integers $A,B:$ $$ (k+A)(k+t+B) = k^2 +kt +(A+B)k + At. $$ Compare $$ k^2 + kt - 9011 t, $$ we need $A+B = 0,$ $A = -9011.$ So $B = 9011.$ Check again, $$ (k - 9011)(k+t+9011) = k^2 + kt -9011 t - 9011^2. $$ Lots of ways to write, $$ (k - 9011)(k+t+9011) + 9011^2 = k^2 + kt -9011 t , $$ $$ (k - 9011)(k+t+9011) + 9011^2 + 3028 = k^2 + kt -9011 t + 3028 = 0, $$ $$ (k - 9011)(k+t+9011) + 9011^2 + 3028 = 0,$$ $$ (k - 9011)(k+t+9011) = - 9011^2 - 3028 = -81201149 = - 8147 \cdot 9967$$ There are several outcomes, $$ k - 9011 = -8147, \; \; k+t+9011 = 9967 $$ gives your $k = 864$ $$ k - 9011 = 1, \; \; k+t+9011 = -81201149 $$ gives $k = 9012$

Will Jagy
  • 139,541
2

Your first equation is equivalent to $$ k^2 + k + 5 = (13 - k) x $$ where $k$ and $x$ are integers. Thus $$ x = \frac{k^2 + k + 5}{13 - k} = -k - 14 + \frac{187}{13-k} $$ or $$(x+k+14)(13-k) = 187$$ Thus $13-k$ must be an integer factor of $187$, whose prime factorization is $11 \times 17$. Considering all possible factors ($\pm 1, \pm 11, \pm 17, \pm 187$), the integer solutions are $$ \eqalign{k = -174,& \; x = 161\cr k = -4,& \; x = 1\cr k = 2,& \; x = 1\cr k = 12,& \; x = 161\cr k = 14,& \; x = -215\cr k = 24,& \; x = -55\cr k = 30,& \; x = -55\cr k = 200,& \; x = -215\cr }$$

Robert Israel
  • 448,999