# Congruence mod $n+1$ of radix-$n$ integers

Let $a$ and $b$ be distinct positive integers. Prove (or disprove) that if $a\equiv b\pmod{n+1}$, then the radix-$n$ representation of $a$ and $b$ differ in at least two digits.

Edit to add some more details:

I arose at this conjecture while trying to find a simple way to partition integers into a small number of sets in such a way that no two integers in a set differ by only a single digit. I have only verified for a relatively small number of cases, but it seems to work. It makes some intuitive sense to me for reasons that are tricky to verbalize.

As for an attempt at a proof, my initial thought was to observe that if $a$ and $b$ differ in only a single digit, then $a-b=cn^d$ for some integers $1\leq c<n$ and $d\geq0$. Then, if $a\equiv b\pmod{n+1}$, then $(n+1)\mid cn^d$. But from here I'm stuck.

• Ooh...by the way, do not forget to include your own thoughts and efforts on the question. Have you worked on starting a proof, or searched for a counterexample? We need to see such efforts, in your question post, so that we may help lead you to what you may need to finish. Oh...let me also add, we don't provide answers and proofs on demand. We ask, however, that you "pay" for help by showing you've seriously put effort into proving/finding a counter-example. Jun 25, 2017 at 23:32
• @amWhy: My bad. I've added a bit more details, including the basic approach I've tried so far. Jun 25, 2017 at 23:59
• @zappa then n+1 | cn^d But $\;\gcd(n+1, n)=1\,$, so $\;\cdots\;$ P.S. Also note that, the way you wrote it, $c$ could also be negative so the right condition is rather $0 \lt |c| \lt n\,$.
– dxiv
Jun 26, 2017 at 0:01
• Well, that's a great start. It always helps, and never hurts, to include such background. That can be useful for answerers to launch from. Jun 26, 2017 at 0:02
• @dxiv oh crap, now I feel silly. I blame it on a new baby and severe lack of sleep. Thank you! If you finish that proof as an answer I'll accept it; otherwise, I'll do that myself in a little while. Jun 26, 2017 at 0:05

Assume without loss of generality that $a>b$. If $a$ and $b$ differ in just one digit, then there must exist integers $c\in[1..n-1]$ and $e\geq0$ such that $a-b=c\,n^e$. Now, since $a\equiv b\bmod{(n+1)}$, it follows that $(n+1)\mid c\,n^e$. But $\gcd(n,n+1)=1$, so (using an easy generalization of Euclid's Lemma to arbitrary integers) this can only happen when $(n+1)\mid c$, which is clearly impossible due to the restriction that $c\in[1..n-1]$.
(For the claim that $\gcd(n,n+1)=1$: using the fact that $\forall x,y\in\mathbb{N},\gcd(x,y)=\gcd(x,y-x)$, it follows immediately that $\gcd(n,n+1)=\gcd(n,1)=1$.)