Same Remainders (Mathathon Problem 6)

The numbers 5841 , 9337 5841, 9337 and 11085 11085 all leave the same remainder r r when divided by a 4-digit positive integer x x .

Find the value of 2 x 3 r 2x - 3r .


The answer is 1705.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

17 solutions

I will post most common solution after a few solutions have been posted.

Julie Éthier
Mar 28, 2021

Agent T
Mar 28, 2021

G i v e n : D i v i s o r = x \boxed{\textcolor{#20A900}{Given:}\textcolor{#20A900}{Divisor=x}} (a 4 digit number)

Using the relation between dividend,divisor, quotient and remainder i.e,

D i v i d e n d = Q u o t i e n t d i v i s o r ( x ) + r e m a i n d e r ( r ) \boxed{\textcolor{#D61F06}{Dividend=Quotient*divisor(x)+remainder(r)}}

11085 = t x + r \textcolor{#69047E}{✩11085=t*x+r} ,where t is the q u o t i e n t \textcolor{#3D99F6}{quotient}

9337 = a x + r \textcolor{#69047E}{▼9337=a*x+r} ,where x is the q u o t i e n t \textcolor{#3D99F6}{quotient}

5841 = n x + r \textcolor{#69047E}{□5841=n*x+r} ,where n is the q u o t i e n t \textcolor{#3D99F6}{quotient}

Subtracting \textcolor{#69047E}{□} from \textcolor{#69047E}{▼} and \textcolor{#69047E}{▼} from \textcolor{#69047E}{✩} we get,

  • 3496 = ( t a ) x + 0 \textcolor{#3D99F6}{3496=(t-a)x+0}

  • 1748 = ( a n ) x + 0 \textcolor{#3D99F6}{ 1748=(a-n)x+0}

= > x => x divides both 3496 \textcolor{#3D99F6}{3496} and 1748 \textcolor{#3D99F6}{1748} perfectly

Recalling the fact that x is a 4 \textcolor{#20A900}{4 } digit no. which divides both 3496 \textcolor{#3D99F6}{3496} and 1748 \textcolor{#3D99F6}{1748} perfectly,

we can conclude that x = 1748 \textcolor{#69047E}{\boxed{x=1748}}

Calculating the value of r:

Dividing any dividend (I preferred dividing 5841 )by 1748 should leave the r e m a i n d e r = 597 \textcolor{#CEBB00}{remainder=597}

Substituting the values of x x and r r in : 2 x r \boxed{\textcolor{#69047E}{2x-r}} We get 1705 \boxed{\textcolor{#D61F06}{1705}}

Hence 1705 \boxed{\textcolor{#3D99F6}{1705}} is the correct answer!

required calculations required calculations

Devbrat Dandotiya
Mar 25, 2021

We have three numbers, 5841 , 9337 , 11085 5841, 9337, 11085 giving the same remainder r r under division by a four digit unknown number x x , i.e

Dividend= Divisor × Quotient + Remainder \text{Dividend= Divisor × Quotient + Remainder}

5841 = x a + r and 9337 = x b + r and 11085 = x c + r 5841= xa+r \text{ and } 9337= xb+r \text{ and } 11085= xc+r

Note that subtracting any two number from the given three above, i.e ( b x + r ) ( a x + r ) = ( b a ) x (bx+r)-(ax+r)= (b-a)x or ( c x + r ) ( b x + r ) = ( c b ) x (cx+r)-(bx+r)=(c-b)x or ( c x + r ) ( a x + r ) = ( c a ) x (cx+r)-(ax+r)=(c-a)x gives us a difference that is divisible by the given unknown divisor x x . This way we have three differences,

( b a ) x = 9337 5841 = 3496 and ( c b ) x = 11085 9337 = 1748 and ( c a ) x = 11085 5841 = 5244 (b-a)x= 9337-5841= 3496 \text{ and } (c-b)x= 11085-9337=1748 \text{ and } (c-a)x=11085-5841= 5244

Thus 3496 , 1748 , 5244 3496, 1748, 5244 , are all divisible by x x and since gcf ( 5841 , 9337 , 11085 ) = 1 \text{gcf}(5841,9337,11085)=1 , it follows that gcf ( 3496 , 1748 , 5244 ) = x \text{gcf}(3496, 1748, 5244)=x . Since gcf ( 3496 , 1748 , 5244 ) = 1748 \text{gcf}(3496, 1748, 5244)= 1748 , x = 1748 x=1748 , 1748 1748 divides 3496 , 1748 3496, 1748 and 5244 5244 . Now we can find r r by dividing either one of 5841 , 9337 , 11085 5841, 9337, 11085 by x x and observing the remainder,

5841 = 1748 × 3 + 597 and 9337 = 1748 × 5 + 597 and 11085 = 1748 × 6 + 597 gives r = 597 5841= 1748×3+597 \text{ and } 9337= 1748×5+597 \text{ and } 11085=1748×6+597 \text{ gives } r=597

Thus,

2 x 3 r = 2 ( 1748 ) 3 ( 597 ) = 3496 1791 = 1705 2x-3r= 2(1748)-3(597)= 3496-1791= \boxed{1705}

Siddhesh Umarjee
Mar 31, 2021

Let 5841 = a x + r 5841 = ax + r , 9337 = b x + r 9337 = bx + r & 11085 = c x + r 11085 = cx + r [where a, b & c are integers]

From above Equations:

c x + r b x r = 11085 9337 cx+r-bx-r = 11085-9337

x ( c b ) = 1748 x(c-b) = 1748

Since b & c are integers, (c-b) is integer. Therefore x x is a integer factor of 1748

Factors of 1748 1748 : 1748 , 874 , 437 1748, 874, 437 , and smaller numbers...

But x x is a positive 4-digit integer. The only factor of 1748 1748 which is 4-digit is 1748 1748 itself.

x = 1748 \fbox{ x = 1748}

Dividing any one of the 3 numbers by 1748 will give you remainder r = 597 \fbox{r = 597}

2 x 3 r = 2 1748 3 597 = 1705 2x-3r = 2 \cdot 1748 - 3 \cdot 597 = \fbox{1705}

Kevin Long
Mar 28, 2021

We can write all 3 3 numbers as n x + r nx+r , where n n is a positive integer. Therefore, by subtracting one of the three numbers from another, all the r r terms cancel and we are just left with a multiple of x x . Doing this, we have 9337 5841 = 3496 9337-5841=3496 , and 11085 9337 = 1748 11085-9337=1748 . We now have two cases; x = 1748 x=1748 , and x = 3496 x=3496 ( x = 3 × 1748 = 5244 (x=3\times1748=5244 doesn't work because 5841 5841 and 9337 9337 would have different remainders.). Evaluating these cases separately, we get,
1 ) x = 1748 \huge 1) x=1748
The remainder will be r = 5841 1748 × 3 = 5841 5244 = 597 r= 5841- 1748\times3=5841-5244=597 , so r = 597 r=597 . Checking our work, we subtract 597 597 from all three numbers, and we get 5244 5244 , 8740 8740 , and 10488 10488 , which are all multiples of 1748 1748 .
2 ) x = 3496 \huge 2) x=3496
For this case, r = 5841 3496 = 2345 r=5841-3496=2345 . Checking our work, we subtract 2345 from all three numbers, and we get 3496 3496 , 6992 6992 , and 8740 8740 . 8740 8740 is not a multiple of 3496 3496 , so x = 3496 x=3496 is impossible. That just leaves 1748, so the answer is 1748 \boxed{1748} .



Jeff Giff
Mar 26, 2021

From the question we have: 5841 9337 11085 r ( m o d x ) ( x > r > 0 ) . 5841\equiv 9337 \equiv 11085\equiv r \pmod x~~~(x\gt r\gt 0).

From Brilliant wiki ,
For a positive integer n n , the integers a a and b b are congruent m o d n \bmod ~n if their remainders when divided by n n are the same.
Another way of defining this is that integers a a and b b are congruent m o d n \bmod~n if their difference ( a b ) (a-b) is an integer multiple of n n , that is, if a b n \frac{a-b}{n} has a remainder of 0 0 .

Using the second law in reverse, we can sufficiently say since 11085 9337 = 1748 , 9337 5841 = 3496 11085-9337=1748,~~9337-5841=3496 and 11085 5841 = 5244 11085-5841=5244 , x x is a common factor of the three.
Therefore x x is the factor of gcd ( 1748 , 3496 , 5244 ) = 1748 \color{#D61F06}\text{gcd}(1748,3496,5244)=1748 . The only factor of 1748 1748 that has four digits is 1748 1748 itself. Since 5841 ÷ 1748 = 3...597 5841\div 1748=3...597 , r = 597 r=597 .
2 x 3 r = 2 × 1748 3 × 597 = 3496 1791 = 596. \therefore 2x-3r=2\times 1748-3\times 597=3496-1791=596.

Atin Gupta
Mar 26, 2021

11085 9337 5841 r ( m o d x ) 11085 ≡ 9337 ≡ 5841 ≡ r (mod x)

Now, 11085 9337 1748 r r 0 x ( m o d x ) 1748 x ( m o d x ) 11085 - 9337 ≡ 1748 ≡ r - r ≡ 0 ≡ x (mod x) \Rightarrow 1748 ≡ x (mod x)

This implies that 1748 is a multiple of x. Hence, x is a factor of 1748.

x ϵ 1 , 2 , 4 , 19 , 23 , 38 , 46 , 76 , 92 , 437 , 874 , 1748 x \epsilon {1, 2, 4, 19, 23, 38, 46, 76, 92, 437, 874, 1748} (Factors of 1748)

But, x > 1000, hence x = 1748.

We can check: 11085, 9337, and 5841, each gives a remainder of 597 when divided by 1748.

11085 9337 5841 597 ( m o d 1748 ) 11085 ≡ 9337 ≡ 5841 ≡ 597 (mod 1748)

r = 597 , x = 1748 , 2 x 3 r = 3496 1791 = 1705 ∴ r = 597, x = 1748, 2x - 3r = 3496 - 1791 = \boxed{1705}

Below is a different approach, in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
x = []                               # List of possible values for x
r = []                               # List of possible values for r

for n in range(1000, 5841):          # Check for each number between 999 and 5841
    if 11085%n == 5841%n == 9337%n:  # If the remainders are same
        x.append(n)                  # Put this number in the list of possible values of x

for n in x:                          # For a possibility for x
    r.append(11085%n)                # Put the remainder in the list of possible values for r

for a in range(len(x)):              # For every possibility of x:
    print(2*x[a] - 3*r[a])           # Print 2x-3r

1
1705

Sundar R
Mar 26, 2021

All of the numbers are of the form n(i) = q(i)*x + r where n(1) = 5841, n(2) = 9337 and n(3) = 11085. q(i) are the quotients and r is the common remainder. So if we subtract the numbers from one another, the difference should be divisible by x.

11085 - 9337 = 1748. Since we are told that x is a 4 digit number, most likely it will be 1748. Just for confirmation, 9337 - 5841 = 3496 = 2 * 1748. So, it is clear that x = 1748. After that, it is a simple matter of dividing any of the numbers by 1748 and finding the remainder r which we find is 597. Then one can evaluate the given expression by plugging in values

Aditya Mittal
Mar 26, 2021

I figured that x will be less than or equal to 9337 - 5841 and put it in my program:

1
2
3
4
5
#Since x is a 4 digit number and less than 3496, this will try every number from 1000 to 3496
#I had to use brute force, I couldn't figure out anything else!
for x in range(1000,3497):
    if(5841%x == 9337%x == 11085%x):
        print(2*x - 3*(5841%x))

Newton Kayode
Mar 26, 2021

We can demonstrate this using a simple example 4 mod 3=1 7 mod 3 =1 10 mod 3 =1 13 mod 3 =1 You can see that all of the starting numbers have a difference of 3. So 11085, 9337 and 5841 should have the same difference right? No BUT going back to our previous example, 4 mod 3 =1 10 mod 3 =1 16 mod 3 =1 So they don't all have to have the exact same difference but they should be related So 9337-5841=3,496 and 11,085-9,337=1,748. 3,496/1,748=2. So it is actually 5841 mod x=r 9337 mod x=r 11085 mod 2x=r So x= 1748 and 2x=3,496 and when you calculate it, 5841 mod 1748=597=r. So, (2* 1748)-(3* 597)= 3496-1791= 1705 \boxed{1705}

Morris Pearl
Mar 25, 2021

The three given integers are all equal mod x. Therefore, the difference of any two of them must be zero mod x. The three differences are 1748, 3496 (which is 1748 * 2) and 5244 (which is 1748 * 3).

The prime factors of 1748 are 2, 2, 19, and 23. There is no proper subset of those factors which results in a four digit number, therefor 1748 is the only possible value of x.

The remainder are 597, and therefore 2x - 3r is 1705.

Elijah Frank
Mar 25, 2021

Also in c-b we can do b-a and make a GCD of the 2 numbers: GCD (3496, 1748) = (1748,874,437,92,76,46,38,23,19,4,2,1) the problem is that x It must be a 4-digit number, so the operation that fits here is c-b

Oskar Dobroczek
Mar 25, 2021

As always, words are nice but not very helpful in finding quantitative solutions. So let's use modular arithmetic to figure this boi out. Let a : = 5841 , b : = 9337 , c : = 11085 a:=5841,\;b:=9337,\;c:=11085 and now the question above can be formulated as a r m o d x b r m o d x c r m o d x a b c r m o d x . \begin{aligned} a&\equiv r \mod x\\ b&\equiv r \mod x\\ c&\equiv r \mod x\\ \therefore\; a\equiv b\equiv c &\equiv r \mod x. \end{aligned} We make use of the rule that if c r m o d x c\equiv r \mod x and b r m o d x b\equiv r\mod x , then c b r r 0 m o d x c-b\equiv r-r\equiv 0\mod x and thus c b = 1748 0 m o d x . c-b = 1748 \equiv 0\mod x . Now although x = 874 x=874 would also be possible, we have it in the requirements that it be a 4-digit number and all greater multiples of it do not yield the same remainder when dividing a , b a, b and c c . This means that x = 1748 x=1748 and all that's left to do is find out r r which will be done using a a : 5841 = 3 1748 + 597 r = 597. 5841 = 3\cdot 1748 +597 \implies r = 597 . Now simply plug in 2 1748 3 597 = 1705. 2\cdot 1748 - 3\cdot 597 = 1705.

Zakir Husain
Mar 25, 2021

l e t a , b , c N : let\space a,b,c\in\mathbb{N}: a x = 5841 r . . . . . . . . . . [ 1 ] ax=5841-r..........[1] b x = 9337 r . . . . . . . . . . [ 2 ] bx=9337-r..........[2] c x = 11085 r . . . . . . . . . . [ 3 ] cx=11085-r..........[3] [ 2 ] [ 1 ] ( b a ) x = 3496 [2]-[1]\Rightarrow (b-a)x=3496 [ 3 ] [ 2 ] ( c b ) x = 1748 [3]-[2]\Rightarrow (c-b)x=1748 gcd ( 3496 , 1748 ) = 1748 gcd ( ( c b ) x , ( b a ) x ) \because\gcd(3496,1748)=1748\therefore\gcd((c-b)x,(b-a)x) x i s a c o m m o n f a c t o r o f 3946 a n d 1748 \because x\space is\space a\space common\space factor\space of\space 3946\space and\space 1748 x 1748 x { 1748 , 874 , 437 , 92 , 76 , 46 , 38 , 23 , 19 , 4 , 2 , 1 } \therefore x|1748\Rightarrow x\in\{1748,874,437,92,76,46,38,23,19,4,2,1\} x i s 4 a d i g i t n u m b e r \because x\space is \space 4\space a\space digit\space number x = 1748 \therefore x=1748 [ 1 ] r = 597 [1]\Rightarrow r=597 2 x 3 = 2 × 1748 3 × 597 = 3496 1791 = 1705 \Rightarrow 2x-3=2\times 1748-3\times 597=3496-1791=1705

Avner Lim
Mar 25, 2021

Since 9337 5841 = 3496 9337-5841=3496 , 11085 9337 = 1748 11085-9337=1748 , and 3496 = 1748 × 2 3496 = 1748 \times 2 , x x could probably be 1748 1748 . If x = 1748 x = 1748 , r = 597 r = 597 , which works for 5841 , 9337 , 5841, 9337, and 11085 11085 . So 2 x 3 r = ( 2 × 1748 ) ( 3 × 597 ) = 3496 1791 = 1705 2x-3r = (2 \times 1748) - (3 \times 597) = 3496 - 1791 = \boxed{1705}

x needs to be a factor of 1748. Since it needs to be a 4-digit number, x must be 1748.

Avner Lim - 2 months, 2 weeks ago

For 0 r < x 5841 = a x + r 9337 = b x + r 11085 = c x + r ( c b ) x = 1748 x 1748 Since x is a four digit number x = 1748 Now, 5841 = 1748 × 3 + 597 r = 597 2 x 3 r = 1705 \begin{aligned} &\text{For } 0 \leq r < x \\ &5841=ax+r \\ &9337=bx+r \\ &11085=cx+r \\ \implies &(c-b)x=1748 \\ \implies &x|1748 \\ &\text{Since } x \text{ is a four digit number} \\ \implies &x=1748 \\ &\text{Now,} \\ & 5841=1748 \times 3 + 597 \\ \implies &r=597 \\ \implies &\boxed{2x-3r=1705} \\ \end{aligned}

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...