How can I prove that $\left\lceil \frac{4N}{3} \right\rceil \bmod 4 \ne 1$?

Question

Ok this is for Base $64$ padding.

The length of Base $64$ representation of a sequence of bytes is represented by $\left\lceil \frac{4N}{3} \right\rceil$

The padding should add $M$ characters such that $$\frac{\left(\left\lceil \frac{4N}{3} \right\rceil + M \right)}{4}=0.$$

How can I prove that $M\ne 1$ for all values of $N > 0$?

I created the sequence in Excel and the sequence is $2,3,4,6,7,8,10$ which means the difference is $1-1-2$ that repeats itself. It seems that the number skipped is always $4N+1$ but how to come to this conclusion?

Answer 1

For any $n$, we have either $n=3m$, $n=3m+1$, or $n=3m+2$. Then we just have three cases to consider:

\begin{align*} \left\lceil \frac{4n}{3} \right\rceil &= \left\lceil 4m \right\rceil = 4m \equiv 0 \pmod 4 \\ \left\lceil\frac{4n}{3} \right\rceil &= \left\lceil 4m+\frac{4}{3} \right\rceil =4m+2 \equiv 2 \pmod 4 \\ \left\lceil \frac{4n}{3} \right\rceil &= \left\lceil 4m+\frac{8}{3} \right\rceil =4m+3 \equiv 3 \pmod 4 \end{align*}

Answer 2

Assume for a contradiction that $$\left\lceil\frac{4N}3\right\rceil\equiv1\pmod4;$$ that is, there is an integer $k$ such that $$\left\lceil\frac{4N}3\right\rceil=4k+1.$$ Equivalently, $$4k\lt\frac{4N}3\le4k+1.$$ Multiplying everything by the positive number $\frac34$, it follows that $$3k\lt N\le3k+\frac34\lt3k+1,$$ i.e., $$3k\lt N\lt3k+1.$$ This is impossible; since $3k$ is an integer, there is no integer between $3k$ and $3k+1$.

Answer 3

Divide your data in groups of three bytes. How many bytes are left at the end can be 0,1, or 2: if 0, then each 3 byte group becomes a 4-character base64 group; if 1, we need to characters to encode it and have two padding bytes ==, if $2$ we encode these 16 bits by 3 base64 characters (each encodes 6 bits, so can easily be done) and we add 1 = character. So the incomplete group of 1 or 2 also gets encoded as a 4 character base64 sequence, as all complete groups. We add $0, 2$ resp $1$ padding byte for the cases $N \pmod 3$ equal to $0,1$ or $2$.

So if $N$ is the message length, we have $\lfloor \frac{N}{3}\rfloor$ complete groups of $3$, covering all but the last $N \bmod 3$ bytes, the encoded message has $$4 \left(\lfloor \frac{N}{3} \rfloor + (N \bmod 3)\right)$$ bytes.