# Congruence with variable modulus

I have been working on some problems and one of them has been particularly challenging. The problem is as follows.

Find a non-trivial (meaning more than 1 digit) positive integer a that satisfies:

$a/10 + 3121(a \mod 10) = 0 \mod a$

Here the division operator is meant to denote integer division so algebraically this is equivalent to:

$(\lfloor a/10\rfloor + 3121(a - 10*\lfloor a/10\rfloor)) - a*\lfloor\lfloor a/10\rfloor + 3121(a - 10*\lfloor a/10\rfloor))/a)\rfloor = 0$

I believe there should be some straightforward way to calculate this value. Using a brute force guess and check I found that $a = 101$ satisfied this congruence but I wanted to know if there was a way to analytically work this one out?

• Is the sort of topic covered in a normal number theory book? – frogeyedpeas Jan 14 '13 at 23:01
• If so, what book should I read to learn how to solve this type of problem – frogeyedpeas Jan 14 '13 at 23:01
• Nobody? :( (*thanks Jon for the formatting) – frogeyedpeas Jan 15 '13 at 1:12
• I think your question, as it is now, is pretty confusing: what does "$\,3121(a\pmod {10})\,$" mean? . Then what you say your original expression is equivalent too is waaaay more confusing (at least for me). In fact, I've no idea what is this related to and how did this beast come into life... – DonAntonio Jan 15 '13 at 3:25
• well the 3121 is multiplied to a mod 10 – frogeyedpeas Jan 15 '13 at 3:38

What about $\,a=3\,$? According to what you wrote, and I'm not saying I fully understand how, where, when...of it, we get:

$$\left[\frac{3}{10}\right]+3,121\cdot 3=0+3\cdot 3,121=0\pmod 3$$

And the above , of course, works the same for any positive integer $\,a<10\,$ ...

Added: If you want $\,a\,$ with more than one digit take $\,a=103\,$ :

$$\left[\frac{103}{10}\right]+3,121\cdot (103\pmod{10})=10+3\cdot 3,121=9,373=103\cdot 91$$

• yea, those were what i meant by trivial answers (1 digit) – frogeyedpeas Jan 16 '13 at 0:04

\begin{align} \left \lfloor \dfrac{a}{10} \right \rfloor + 3121 \left (a - 10 \left \lfloor \dfrac{a}{10} \right \rfloor \right ) &= 0 \pmod a \\ \left \lfloor \dfrac{a}{10} \right \rfloor - 31210 \left \lfloor \dfrac{a}{10} \right \rfloor &= 0 \pmod a \\ 31209 \left \lfloor \dfrac{a}{10} \right \rfloor &= 0 \pmod a \\ a \; &\bigg| \; 31209 \left \lfloor \dfrac{a}{10} \right \rfloor \end{align}

Let $a = 10x + y,$ where $1 \le y \le 9,$ then $(10x + y) \; \bigg| \; 31209x$

The divisors of $31209,$ sorted by their units digit, are

   1    101
3    103  303  10403
309  31209


Let $g = \gcd \left(a, \left \lfloor \dfrac{a}{10} \right \rfloor \right) = \gcd(10x+y, x) = \gcd(x, y).$ It follows that the natural numbers $\dfrac{10x+y}{g}$ and $\dfrac x g$ are relatively prime to each other.

\begin{align} (10x + y) \; &\bigg| \; 31209x \cr \left (\dfrac{10x+y}{g}\right ) \; &\bigg| \; 31209 \dfrac x g \cr \left (\dfrac{10x+y}{g}\right ) \; &\bigg| \; 31209 \cr \left( 10\dfrac x g + \dfrac y g \right) \; &\bigg| \; 31209 \cr \end{align}

Define $\Delta(u)$ to be the set of those divisors of 31209 which have a units digit of $u$.

Note that only $\Delta(1)$, $\Delta(3)$, and $\Delta(9)$ are the only non-empty sets.

So, if $g$ is a common divisor of $a = 10x + y$ and $\left \lfloor \dfrac{a}{10} \right \rfloor = x$, then $\dfrac a g = 10\dfrac x g + \dfrac y g$ is a divisor of $31209.$ It follows that the solutions to $a \; \bigg| \; 31209 \left \lfloor \dfrac{a}{10} \right \rfloor$ that correspond to $g$ are

$$a \in g \; \Delta \left( \dfrac y g \right)$$

We can run through the $10$ possible values of y pretty quicky now.

## $y = 0$

$10 \mid 31209 \implies a \in \varnothing$

## $y = 1$

$g = 1$: $\; (10x + 1) \mid 31209 \implies a \in \Delta(1) = \{1, 101\}$

## $y = 2$

$g = 1$: $\; (10x + 2) \mid 31209 \implies a \in \Delta(2) = \varnothing$

$g = 2$: $\; (10(x/2) + 1) \mid 31209 \implies a \in 2\Delta(1) = \{2, 202 \}$

## $y = 3$

$g = 1$: $\; (10x + 3) \mid 31209 \implies a \in \Delta(3) = \{3, 103, 303, 10403 \}$

$g = 3$: $\; (10(x/3) + 1) \mid 31209 \implies a \in 3\Delta(1) = \{3, 303 \}$

## $y = 4$

$g = 1$: $\; (10x + 4) \mid 31209 \implies a \in \Delta(4) = \varnothing$

$g = 2$: $\; (10(x/2) + 2) \mid 31209 \implies a \in 2\Delta(2) = \varnothing$

$g = 4$: $\; (10(x/4) + 1) \mid 31209 \implies a \in 4\Delta(1) = \{4, 404 \}$

## $y = 5$

$g = 1$: $\; (10x + 5) \mid 31209 \implies a \in \Delta(5) = \varnothing$

$g = 5$: $\; (10(x/5) + 1) \mid 31209 \implies a \in 5\Delta(1) = \{5, 505 \}$

## $y = 6$

$g = 1$: $\; (10x + 6) \mid 31209 \implies a \in \Delta(6) = \varnothing$

$g = 2$: $\; (10(x/2) + 3) \mid 31209 \implies a \in 2\Delta(3) = \{ 6, 206, 606, 20806 \}$

$g = 3$: $\; (10(x/3) + 2) \mid 31209 \implies a \in 4\Delta(2) = \varnothing$

$g = 6$: $\; (10(x/6) + 1) \mid 31209 \implies a \in 6\Delta(1) = \{ 6, 606 \}$

## $y = 7$

$g = 1$: $\; (10x + 7) \mid 31209 \implies a \in \Delta(7) = \varnothing$

$g = 7$: $\; (10(x/7) + 1) \mid 31209 \implies a \in 7\Delta(1) = \{7, 707 \}$

## $y = 8$

$g = 1$: $\; (10x + 8) \mid 31209 \implies a \in \Delta(8) = \varnothing$

$g = 2$: $\; (10(x/2) + 4) \mid 31209 \implies a \in 2\Delta(4) = \varnothing$

$g = 4$: $\; (10(x/4) + 2) \mid 31209 \implies a \in 4\Delta(2) = \varnothing$

$g = 8$: $\; (10(x/8) + 1) \mid 31209 \implies a \in 8\Delta(1) = \{8, 808 \}$

## $y = 9$

$g = 1$: $\; (10x + 9) \mid 31209 \implies a \in \Delta(9) = \{309, 31209 \}$

$g = 3$: $\; (10(x/3) + 3) \mid 31209 \implies a \in 3\Delta(3) = \{9, 309, 909, 31209 \}$

$g = 9$: $\; (10(x/9) + 1) \mid 31209 \implies a \in 9\Delta(1) = \{9, 909 \}$

## Solution Set

    1    2      3     4     5     6     7     8     9
103               206               309
101   202   303   404   505   606   707   808   909
10403             20806             31209