й

Revision ru1, by SHAMPINION, 2019-03-31 20:14:02

It's obvious that $$$l = k \cdot x + c$$$, where $$$c$$$ is one of the {$$$a + b, a - b, -a + b, -a - b$$$}(if c < 0, let's increase it by $$$k$$$).

Now we have to find maximum and minimum $$$q > 0$$$ such that $$$q \cdot l \equiv 0$$$(mod $$$n \cdot k$$$).

Finding maximum is quite easy and not really interesting so I will stop on the second problem.

let $$$d = gcd(k, c)$$$. Let's forget about multiplier $$$q$$$, we will add it in formulas a few later.

$$$d \cdot (k' \cdot x + c') \equiv 0$$$(mod $$$n \cdot k$$$)

let $$$rem = \frac{n \cdot k} {gcd(n \cdot k, d)}$$$, $$$x = c' \cdot y$$$(we can choose any $$$x$$$ from $$$[1; \infty]$$$ so let it divide $$$c'$$$)

$$$c' \cdot (k' \cdot y + 1) \equiv 0$$$(mod $$$rem$$$)

Again let $$$rem' = \frac{rem}{gcd(rem, c')}$$$

$$$k' \cdot y + 1 \equiv 0$$$(mod $$$rem'$$$)

if $gcd(k', rem') > 1, this

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian SHAMPINION 2019-03-31 23:21:03 27
ru2 Russian SHAMPINION 2019-03-31 23:20:33 493 Мелкая правка: 'O(\sqrt[4][k])$' -> 'O(\sqrt[4]k)$' (опубликовано)
ru1 Russian SHAMPINION 2019-03-31 20:14:02 792 Первая редакция (сохранено в черновиках)