Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question

migrated from math.stackexchange.com Feb 27 at 18:39

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

4 Answers 4

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} = Internal`HGCD[vals[[2]], vals[[1]]];
{h23, g23} = Internal`HGCD[vals[[3]], vals[[2]]];
{h13, g13} = Internal`HGCD[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 ---

share|improve this answer
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} *)
share|improve this answer
    
Is there a reason why you used n=n+1 instead of n++? Just curious. –  shrx Feb 27 at 19:24
2  
@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 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.

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

share|improve this answer

Your Answer

 
discard

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