2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Namaste Jun 25 '17 at 23:32
  • $\begingroup$ @amWhy: My bad. I've added a bit more details, including the basic approach I've tried so far. $\endgroup$ – zappa Jun 25 '17 at 23:59
  • $\begingroup$ @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\,$. $\endgroup$ – dxiv Jun 26 '17 at 0:01
  • $\begingroup$ 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. $\endgroup$ – Namaste Jun 26 '17 at 0:02
  • $\begingroup$ @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. $\endgroup$ – zappa Jun 26 '17 at 0:05
0
$\begingroup$

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

$\endgroup$

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.