5
$\begingroup$

In computer programming languages we have an operator called % which expresses the remainder between two numbers. For example $123\%100 = 23$.

I have an equation evolving this operator, namely,

$$\frac{5}{3}(N\%36) - \frac{2}{3}(N\%6) + 2(N\%25) - (N\%5) = (2N)\%100$$

Is there some easy way to solve this equation in $N$ or at least count the solutions within some range of numbers? (I would like some techniques from number theory rather than a brute force solution, which I have already calculated myself.)

$\endgroup$
2
+100
$\begingroup$

Here's a non-brute force proof that: $$N\equiv 0,1,2,3,4\textrm{ or }5\ (\operatorname{mod 30}),$$ i.e. $N=30a+b$ for some integers $a$ and $b$, with $b = 0,1,2,3,4,$ or $5$. Let $N\%d$ denote the minimal nonnegative remainder after division of $N$ by $d$, such that $0\leq N\%d < N$, where $N$ and $d$ are nonnegative integers. Then $$N\%36 = N\%6 + 6k,$$ where $k = 1, 2, 3, 4,$ or $5$. Similarly: $$N\%25 = N\%5 + 5l$$ where $l = 1, 2, 3,$ or $4$, and $$(2N)\%100 = (2N)\%25 + 25m$$ where $m = 1, 2$, or $3$. Note furthermore that we have $$(2N)\%25 = 2(N\%25) - 25r,$$ where $r=0\textrm{ or }1$.

The above formulae substitute into your equation as follows: $$\frac{5}{3}(N\%36) - \frac{2}{3}(N\%6) + 2(N\%25) - (N\%5) = (2N)\%100$$ $$\frac{5}{3}\left[ N\%6 + 6k \right] - \frac{2}{3}(N\%6) + 2\left[ N\%5 + 5l \right] - (N\%5) = 2(N\%25) - 25r + 25m$$ $$N\%6 + 10k + N\%5 + 10l = 2\left[ N\%5 + 5l \right] - 25r + 25m$$ $$N\%6 - N\%5 = -10k - 25r + 25m$$ $$N\%6 - N\%5 = 5(5m -2k - 5r). \tag{$\star$}$$

Eq. $(\star)$ implies that $N\%6 - N\%5$ is divisible by five. However, remember that $\%$ was defined such that $0\leq N\%d < N$: thus $N\%6 \leq 5$ and $N\%5 \leq 4$. Thus, the only way for this difference to be divisible by $5$ is if $$N\%6 - N\%5 = 0\textrm{ or }5.$$ Suppose that $N\%6 - N\%5 = 0$. Then $N\%6 = N\%5$, and since $0 \leq N\%5\leq 4$, we have: $$N\%6 = N\%5 = 0,1,2,3,\textrm{ or }4. \tag{$*$}$$ You can convince yourself$^1$ that Eq. $(*)$ implies $$N\%30 = 0,1,2,3,\textrm{ or }4,$$ i.e. $$N\equiv 0,1,2,3\textrm{ or }4\ (\operatorname{mod 30}).$$ The other case, $N\%6 - N\%5 = 5$ implies $N\%5=0$ and $N\%6=5$, which implies $N\%30=5$, i.e. $N \equiv 5\ (\operatorname{mod 30})$. Q.E.D.

This type of logic can probably be extended to give the complete solution to your problem, but I don't want to flog it to death. One first next step would be to show that the case $N\%6=5$, $N\%5=0$ can't occur.

This should anyway give you an idea of how basic arithmetic arguments can be brought to bear on this kind of problem. Sometimes things come to this when all else fails in research-level elementary number theory, for example in the proofs that an odd perfect number would have to have more than $k$ distinct prime factors, for various values of k.

$^1$One way to convince yourself is via the Chinese remainder theorem, but it isn't the only way.

$\endgroup$
  • $\begingroup$ While this works out nice enough for the $\mod 30$ case, I'd hate to see the amount of work required to show that the only shifts by $30$ (mod $900$) are $0,30,360,390,720$ (i.e. $30$ times $0,1,12,13,24$). These numbers have little apparent cohesion. $\endgroup$ – awwalker May 25 '13 at 6:21
  • $\begingroup$ @AWalker Ah but I disagree! Obviously $0,360,720 \equiv 0\ (\operatorname{mod }360)$ and $30,390 \equiv 30\ (\operatorname{mod }360)$. $\endgroup$ – Douglas B. Staple May 25 '13 at 12:10
3
$\begingroup$

We note that $N$ solves your equation if and only if $900+N$ solves your equation. Then, some quick code (e.g. the following)

   Select[Range[900], 5 Mod[#, 36]/3 - 2 Mod[#, 6]/3 + 2 Mod[#, 25] - Mod[#, 5]
       == Mod[2 #, 100] &]

gives the following solutions in $[1,900]$:

$$\{1, 2, 3, 4, 30, 31, 32, 33, 34, 360, 361, 362, 363, 364, $$ $$390, 391, 392, 393, 394, 720, 721, 722, 723, 724, 900\}$$

We see that each solution occurs in a block of $4$, so we can think of our solutions as elements of $$\{0,30,360,390,720\},$$ shifted by an element of $$\{i+900j : i \in [0,4],\, j \in \mathbb{Z}\}.$$

$\endgroup$
  • $\begingroup$ This is essentially a brute force approach isn't it? Maybe there is a solution which does not require a computer. $\endgroup$ – Mark May 20 '13 at 1:32
  • $\begingroup$ @Mark I doubt so. Pure mathematics rarely deals with such "mixed mod" problems, because number theory typically vies the solutions to modular equations as lying in some ring of residues. Here, the best we can do is identify a minimal period ($900$) and, yes, brute force thereafter. $\endgroup$ – awwalker May 20 '13 at 2:39
  • $\begingroup$ This seems to be such a natural question to ask though. I take a a number and tell you some facts about its remainders. Then you try to deduce what my number was! $\endgroup$ – Mark May 21 '13 at 15:55
  • $\begingroup$ The unnaturality stems from the fact that (mathematically), there's little that says that $9 \mod 5$ shouldn't just as equally be $4$ or $-1$, e.g. $\endgroup$ – awwalker May 21 '13 at 20:09
  • $\begingroup$ But you could just as well define the a%b operator to give you the unique remainder specified in the division algorithm: a = b*q + r $\endgroup$ – Mark May 22 '13 at 3:09

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.