In the Lucas Lehmer Primality Test, the following identity is used: $q\equiv (q\mod 2^n)+\lfloor\frac{q}{2^n}\rfloor(\mod 2^n-1)$.
This allows the modulus operation to converge with only addition after observing a that the least significant $n$ bits of $k$ plus the remaining bits of $k$ are congruent to $k$ modulo $2^n-1$ (https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test).
This, I assume, is part of the reason the Lucas-Lehmer test is so efficient for astronomically large numbers. Just as the Lucas-Lehmer test requires many mods to be taken, so too does Proth's test, which has also given us some of the largest primes we know of. Therefore my question is whether there is an analogue in Proth's test: $q\mod k2^n+1$.
Is there any way to similarly simplify the complexity of this step, or is the efficiency of Proth's test accomplished some other way, or do people simply brute force through these computations?