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<r-1$ (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 :)


While I'm not sure how to make the OP's idea work, the following is a solution to the problem he poses.

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)$.

That should be all the cases.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.