# Representation of an integer / Euclidean algorithm

Let $$r \in \mathbb{N}$$ be a natural number. Let $$L \geq 2(r-1)²$$ A paper (on quantum information theory, I'm not an expert in number theory or so...) I'm recently reading now says

"One can easily check that $$L$$ can be represented as $$L = a(r-1)+br$$ where $$a, b \in \mathbb{Z}$$ are positive integers and $$K = a + b$$ is even."

My first attempt was of course to apply something like the euclidean algorithm, which gives us $$L = k(r-1)+m$$ where $$k, m$$ are positive integers, $$m (I tried to apply euclidean algorithm for $$r$$ instead of $$r-1$$ at first, but this seems to be more useful...)

As we have $$L = k(r-1) + m \geq 2(r-1)²$$ with $$m \leq r-2$$, we know $$k+1-m-2 \geq 2r(r-1) -(r-2)-2 \geq 2r² -3r -1 \geq (r-1)²$$ for all $$r\geq 2$$. (The case $$r=1$$ is not interesting.)

Therefore we can write $$L = (k+1)(r-1)+m-r+1 = (k+1-m-2)(r-1)+(m+1)r$$ where now $$(k+1-m-2), (m+1)$$ are positive integers. But their sum equals $$(k+1-m-2)+(m+1)=k$$ which of course does not have to be even.

Can somebody give me a hint how to manipulate this way of writing $$L=a(r-1)+br$$ where $$a+b$$ is even?

This whole thing is a little weird, if you consider e.g. $$r=5, L=33\geq 32$$, you could write $$33=5r+2(r-1)$$ where $$5+2$$ is not even, but you also can write $$33=r+7(r-1)$$ where $$1+7$$ is even (I don't know if an expert in stuff like this would consider this as weird, but I do...)

Thanks for any help :)

First suppose $$(r-1) \nmid L$$. Notice that the condition that $$a,b$$ exist so that $$L = a(r-1) + br$$ is equivalent to saying that $$a,b$$ exist so that $$r-1 = \frac{L-b}{a + b}$$. Choose $$b$$ so that $$L-b = 2k(r-1)$$, where $$k$$ is chosen so that $$2k(r-1)$$ is the largest multiple of $$2(r-1)$$ less than or equal to $$L$$. Then we must have $$a + b = 2k$$ and that $$0 < b \leq r-1$$. Because $$k \geq r-1$$, it follows that $$a > 0$$.
Now suppose $$L = m(r-1)$$ for some odd number $$m$$. Then take $$b = r-1$$ and $$a = m-r$$.
Now suppose $$L = 2m(r-1)$$ for some odd number $$m$$. Then take $$b = 2(r-1)$$ and $$a = 2(m-r)$$.