I am working on a small program in sage that encodes messages using RSA encryption in an attempt to show the process step by step, along with mathematical justifications for each step, for a presentation. This question deals with the mathematics behind it, so i figured it would be better to post here than at the crypto stack exchange forum.
In RSA, you have a large modulus, n. When a message gets encoded, it is broken up into blocks of k letters each, and we must be sre that these blocks are less than n (the modulus). What is, then, the largest block size k that can be used? I believe it is
$$ k = \left\lceil \frac{ln(n+1)}{ln(256)} \right\rceil -1 $$
But can not figure out how to prove/show this?
RSA allows the encryption of any message $M$ between 0 and $n-1$. Technically $M$ should be coprime to $p$ and $q$ ($pq=n$), but realistically we do not need to worry about this because finding an $M=kp$ is equivalent to factoring $n$. Moreover, RSA still works with such an $M$ (although the standard proof does not show this).
So any $M$ between 0 and $n-1$ has the property that $M^{ed}=M \bmod n$. You ask how to encode a longer message? The obvious way is to break the longer message into a base-$n$ number and encode each "digit." In other words, treat your longer message $M^*$ as a very large integer and let $M^*=jn+k$ where $k<n$ and use $k$ as an input to RSA. Repeat.
Your question seems to want to do this in base-256 instead. The expression you gave is computing
$$\lceil \log_{256} (n+1) \rceil $$
which gives the number of bytes required to accommodate a "chunk" of $M^*$. Is this what you're after?
Finally, I should say that no one really breaks a message down and encrypts each chunk like this using RSA. First it's insecure, and second it's inefficient (since RSA is slow compared to symmetric algorithms). Instead you would pick a symmetric key $K$ and encrypt $K$ with RSA, then append (say) the AES-CBC encryption of $M^*$ under $K$.