# Finding a number which has the same remainder when dividing certain other numbers

I am having some trouble with formulating my problem in Mathematica for this question:

Is there a number greater than 1 which leaves the same remainder when it divides into 1716, 2154, and 4271? (For example, 4 does not work because if we divide it, we get remainders of 0, 2 and 3). Answer the question by checking all numbers starting at 2 and ending at 1716.

I am a bit confused on how to set it up. I want to say it will be a While command that starts at n = 2 but I don't know how to proceed.

-

## migrated from math.stackexchange.comFeb 27 '14 at 18:39

This question came from our site for people studying math at any level and professionals in related fields.

A heuristic way to narrow the search range is to assume that the common remainder is not too large, and hence that the ratios will not change by much.

So set up three ratios for values minus remainder, and evaluate at remainder=0.

fracs =
Apply[Divide, Partition[vals - k, 2, 1, {1, -2}], {1}]
nfracs = N[fracs /. k -> 0]

(* Out[608]= {(1716 - k)/(2154 - k), (2154 - k)/(4271 - k), (4271 - k)/(
1716 - k)}

Out[609]= {0.796657, 0.504332, 2.48893} *)


Now guess that the actual values will be within 2% of these.

eps = 1/50;
Reduce[Thread[nfracs - nfracs*eps <= fracs <= nfracs + nfracs*eps], k]

(* During evaluation of In[606]:= Reduce::ratnz: Reduce was unable to solve the system with inexact coefficients. The answer was obtained by solving a corresponding exact system and numericizing the result. >>

Out[607]= -59.3545 <= k <= 55.5142 *)


This gives a viable search space for the remainder. So now we check those values. We're looking for values for which there is a common nontrivial gcd.

Select[
Apply[GCD, Table[vals - k, {k, -59, 55}], {1}], # > 1 &]

(* Out[632]= {73, 73} *)


So we find that 73 is the number that will leave a common remainder.

--- edit ---

Here is a related approach. Also heuristic, and uses some number theory, but it avoids mucking with a search space. The heuristic idea is that, provided the common remainder is not terribly large, the initial quotients in the Euclidean remainder sequence for pairs of these values will be the same as those for same pairs with remainder subtracted. We can get the multiplier matrix corresponding to the "upper half" of these quotients using the "half-gcd". (There are numerous references to this. (With apologies for self reference,) I list several in here

{h12, g12} = InternalHGCD[vals[[2]], vals[[1]]];
{h23, g23} = InternalHGCD[vals[[3]], vals[[2]]];
{h13, g13} = InternalHGCD[vals[[3]], vals[[1]]];
Expand[{h12.({vals[[2]], vals[[1]]} - k),
h23.({vals[[3]], vals[[2]]} - k), h13.({vals[[3]], vals[[2]]} - k)}]


(* {{402 - k, 36 + k}, {2117, 37 - k}, {-37 + k, 2228 - 3 k}} *)

When the heuristic is on target, all these values will have some common divisor. This tells us a few things. One is that our common remainder, k, is likely to be related to 37 (we know it is 37...). Maybe more important is that this divisor must divide 2117. Checking its divisors shows 73 in the mix, and it's easy to see from there that k is 37.

Even when this implementation of the heuristic takes too large a step, one can probably do similar things with continued fractions, not jumping as far toward the gcd in the Euclidean remainder sequence, and work with the analogous expressions to what I show above. Mind you, I've no intention of working through the details.

--- end edit ---

-
n = 2;
While[!Equal@@Mod[{1716, 2154, 4271}, n] && n<1716, n=n+1];
n

(* Out: 73 *)


And it's easy to check:

Mod[{1716, 2154, 4271}, 73]

(* Out: {37, 37, 37} *)

-
Is there a reason why you used n=n+1 instead of n++? Just curious. – shrx Feb 27 '14 at 19:24
@shrx Taste? I personally find n=n+1 to be a bit more clear. I am aware that a good C compiler will replace n=n+1 with n++ but I think there's not much difference in Mathematica. If anything, n=n+1 is very slightly faster. – Mark McClure Feb 27 '14 at 19:36

You can use

FindInstance[1716 == a1 k + r && 2154 == a2 k + r && 4271 == a3 k + r && a1 > 0 && k > 1,
{a1, a2, a3, k, r}, Integers]


or

Reduce[1716 == a1 k + r && 2154 == a2 k + r && 4271 == a3 k + r && a1 > 0 && k > 1,
{a1, a2, a3, k, r}, Integers]


The first one will tell you that 73 is such a number and the second one will tell you that 73 is the only such number.

This is the way to put the question directly to Mathematica without telling it what approach to use. It might or might not give an answer. If it does, it won't tell you how it arrived to it. In this sense I find Mark's answer more convincing about the fact that 73 is the only such number.

-
Pick[Range[2, 1716], SameQ @@@ Transpose[Mod[#, Range[2, 1716]] & /@ {1716, 2154, 4271}]]

(* {73} *)
`

Will output any and all up to the range limit, move it to 4271 to show 73 is the only answer...

-