2

[preface, i'll use '%' as the modulo or remainder operator, as it is in C and many other programming languages, where for example 10 % 7 == 3]

i'm looking for an algorithm to solve for n in

(A*n + B) % C == 0

where A, B, and C are all positive integers.

i have additional constraints on my particular problem that i don't think are important for the solution. (namely, A is less than C, A is a power of 3, C is a power of 2, and B is odd, all of which i believe imply that n must be odd.) (and yes, i'm toying with Collatz here)

i can brute force this (try all possible n from 0 to C-1), but that will become time consuming as C increases. i could also try to binary search for it, which would be a performance improvement, but i'm looking for a more efficient algorithm.

Gorilla Sapiens
  • 29
  • 1
  • You'll find some code optimization here, and code in the comments/chat: https://math.stackexchange.com/questions/3454674/calculate-the-maximum-in-the-collatz-sequence – Collag3n Apr 17 '21 at 21:20
  • See the linked dupes for the standard theory and algorithms for solving linear congruences. – Bill Dubuque Apr 17 '21 at 22:08

1 Answers1

0

Translating to more standard number theory, you want a solution to $$ An\equiv-B\pmod C $$ The first step to a solution is to solve $$ Am\equiv 1\pmod C $$ We then get $n=-Bm$ by multiplying both sides with $-B$.

The extended Euclidean algorithm gives you two integers $m, m'$ such that $$ Am+Cm'=1 $$ (as your additional constraints tell us that $\gcd(A,C)=1$). This finishes the solution. A solution between $0$ and $C$ is not guaranteed in this case, so taking $n\%C$ at the end will give you that.

Arthur
  • 193,927
  • 14
  • 168
  • 299
  • But the first step fails if $A$ and $C$ are not coprime. But not to worry since this is FAQ which has been answered hundreds of times in the past. *Please* strive not to add more dupe answers to dupes of FAQs. – Bill Dubuque Apr 17 '21 at 22:10
  • @BillDubuque This time I actually _did_ a rudimentary search for dupes and still didn't find any good ones. Please stop hounding me about it, I have decided it is impossible. (I'm sure some can do it, but I just can't.) – Arthur Apr 18 '21 at 04:13
  • so... any clues on how to do the first step (Am == 1 (mod C) ??? – Gorilla Sapiens Apr 18 '21 at 21:57
  • @GorillaSapiens Yes, the extended Euclidean algorithm, as I said. – Arthur Apr 19 '21 at 07:08