where k is an integer. a, b, and M are fixed values.
Due to modulo max value is M-1 but it may/may not be achievable, depending on the value of a and b.
if gcd(b,M) = 1 then b is invertible modulo M. Thus M-1 is achievable.
a+k.b congruent M - 1 (mod M)
So, if we select k as (M - 1 - a)b' mod M, we can get M-1. (b' is modular multiplicative inverse of b)
what happens if gcd(b,M) != 1?
Recall Bezout's identity: If we have two integers $a,b \in \mathbb{Z}$ such that $gcd(a,b) = d, d \in \mathbb{Z} \implies \exists k,s \in \mathbb{Z}$ such that $ak + bs = d$.
As you've correctly induced, when $gcd(b,M) = 1$, we can say that the max achievable value is $M-1$. A good way to proceed further in describing the max values is to try and leverage Bezout's identity to maybe see a connection along the lines of $gcd(b,M) = d \implies$ max value is dependent on $d$?
Hint: Consider $a \equiv b \pmod{M} \iff a = b + kM, \exists k \in \mathbb{Z}$.
Ok here's the justification for why it is $(M-d) + (a \mod{d})$.
Consider $a + bk \equiv c \mod{M}$. We want to try and make $c$ as large as possible. Rewrite this as $bk \equiv c-a \mod{M}$. Now consider the following:
\begin{gather*} bk \equiv c-a \mod M \implies \exists k', bk = (c-a) + k'M \\ bk + (k')M = (c-a) \end{gather*}
So now denote $gcd(b,M) = d$. By Bezout's identity, we know that we can choose $k,k'$ such that the LHS above goes to $d$. Similarily we can choose them such that it goes to some multiple of $d$. So we choose it as high as possible such that (if we denote that multiple as $m$), $md < M$, which we see can just be $M-d$ (since d | M). Now notice that what we are considering is a potential candidate for $(c-a)$ so we don't want the addition of $a$ to bring $M-d + a \geq M$ for fear of the value resting down to zero. We try then to choose the multiple so that our max value lands in the range $[M-d,M)$ which we can see to be $M-d+(a \mod d)$ (since $(a \mod d) < d$.)