Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.