The numbers 5 8 4 1 , 9 3 3 7 and 1 1 0 8 5 all leave the same remainder r when divided by a 4-digit positive integer x .
Find the value of 2 x − 3 r .
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.
Using the relation between dividend,divisor, quotient and remainder i.e,
✩ 1 1 0 8 5 = t ∗ x + r ,where t is the q u o t i e n t
▼ 9 3 3 7 = a ∗ x + r ,where x is the q u o t i e n t
□ 5 8 4 1 = n ∗ x + r ,where n is the q u o t i e n t
Subtracting □ from ▼ and ▼ from ✩ we get,
3 4 9 6 = ( t − a ) x + 0
1 7 4 8 = ( a − n ) x + 0
= > x divides both 3 4 9 6 and 1 7 4 8 perfectly
Recalling the fact that x is a 4 digit no. which divides both 3 4 9 6 and 1 7 4 8 perfectly,
we can conclude that x = 1 7 4 8
Dividing any dividend (I preferred dividing 5841 )by 1748 should leave the r e m a i n d e r = 5 9 7
Substituting the values of x and r in : 2 x − r We get 1 7 0 5
We have three numbers, 5 8 4 1 , 9 3 3 7 , 1 1 0 8 5 giving the same remainder r under division by a four digit unknown number x , i.e
Dividend= Divisor × Quotient + Remainder
5 8 4 1 = x a + r and 9 3 3 7 = x b + r and 1 1 0 8 5 = x c + r
Note that subtracting any two number from the given three above, i.e ( b x + r ) − ( a x + r ) = ( b − a ) x or ( c x + r ) − ( b x + r ) = ( c − b ) x or ( c x + r ) − ( a x + r ) = ( c − a ) x gives us a difference that is divisible by the given unknown divisor x . This way we have three differences,
( b − a ) x = 9 3 3 7 − 5 8 4 1 = 3 4 9 6 and ( c − b ) x = 1 1 0 8 5 − 9 3 3 7 = 1 7 4 8 and ( c − a ) x = 1 1 0 8 5 − 5 8 4 1 = 5 2 4 4
Thus 3 4 9 6 , 1 7 4 8 , 5 2 4 4 , are all divisible by x and since gcf ( 5 8 4 1 , 9 3 3 7 , 1 1 0 8 5 ) = 1 , it follows that gcf ( 3 4 9 6 , 1 7 4 8 , 5 2 4 4 ) = x . Since gcf ( 3 4 9 6 , 1 7 4 8 , 5 2 4 4 ) = 1 7 4 8 , x = 1 7 4 8 , 1 7 4 8 divides 3 4 9 6 , 1 7 4 8 and 5 2 4 4 . Now we can find r by dividing either one of 5 8 4 1 , 9 3 3 7 , 1 1 0 8 5 by x and observing the remainder,
5 8 4 1 = 1 7 4 8 × 3 + 5 9 7 and 9 3 3 7 = 1 7 4 8 × 5 + 5 9 7 and 1 1 0 8 5 = 1 7 4 8 × 6 + 5 9 7 gives r = 5 9 7
Thus,
2 x − 3 r = 2 ( 1 7 4 8 ) − 3 ( 5 9 7 ) = 3 4 9 6 − 1 7 9 1 = 1 7 0 5
Let 5 8 4 1 = a x + r , 9 3 3 7 = b x + r & 1 1 0 8 5 = c x + r [where a, b & c are integers]
From above Equations:
c x + r − b x − r = 1 1 0 8 5 − 9 3 3 7
x ( c − b ) = 1 7 4 8
Since b & c are integers, (c-b) is integer. Therefore x is a integer factor of 1748
Factors of 1 7 4 8 : 1 7 4 8 , 8 7 4 , 4 3 7 , and smaller numbers...
But x is a positive 4-digit integer. The only factor of 1 7 4 8 which is 4-digit is 1 7 4 8 itself.
x = 1 7 4 8
Dividing any one of the 3 numbers by 1748 will give you remainder r = 5 9 7
2 x − 3 r = 2 ⋅ 1 7 4 8 − 3 ⋅ 5 9 7 = 1 7 0 5
We can write all
3
numbers as
n
x
+
r
, where
n
is a positive integer. Therefore, by subtracting one of the three numbers from another, all the
r
terms cancel and we are just left with a multiple of
x
. Doing this, we have
9
3
3
7
−
5
8
4
1
=
3
4
9
6
, and
1
1
0
8
5
−
9
3
3
7
=
1
7
4
8
. We now have two cases;
x
=
1
7
4
8
, and
x
=
3
4
9
6
(
x
=
3
×
1
7
4
8
=
5
2
4
4
doesn't work because
5
8
4
1
and
9
3
3
7
would have different remainders.). Evaluating these cases separately, we get,
1
)
x
=
1
7
4
8
The remainder will be
r
=
5
8
4
1
−
1
7
4
8
×
3
=
5
8
4
1
−
5
2
4
4
=
5
9
7
, so
r
=
5
9
7
. Checking our work, we subtract
5
9
7
from all three numbers, and we get
5
2
4
4
,
8
7
4
0
, and
1
0
4
8
8
, which are all multiples of
1
7
4
8
.
2
)
x
=
3
4
9
6
For this case,
r
=
5
8
4
1
−
3
4
9
6
=
2
3
4
5
. Checking our work, we subtract 2345 from all three numbers, and we get
3
4
9
6
,
6
9
9
2
, and
8
7
4
0
.
8
7
4
0
is not a multiple of
3
4
9
6
, so
x
=
3
4
9
6
is impossible. That just leaves 1748, so the answer is
1
7
4
8
.
From the question we have: 5 8 4 1 ≡ 9 3 3 7 ≡ 1 1 0 8 5 ≡ r ( m o d x ) ( x > r > 0 ) .
From Brilliant wiki ,
For a positive integer n , the integers a and b are congruent m o d n if their remainders when divided by n are the same.
Another way of defining this is that integers a and b are congruent m o d n if their difference ( a − b ) is an integer multiple of n , that is, if n a − b has a remainder of 0 .
Using the second law in reverse, we can sufficiently say since
1
1
0
8
5
−
9
3
3
7
=
1
7
4
8
,
9
3
3
7
−
5
8
4
1
=
3
4
9
6
and
1
1
0
8
5
−
5
8
4
1
=
5
2
4
4
,
x
is a common factor of the three.
Therefore
x
is the factor of
gcd
(
1
7
4
8
,
3
4
9
6
,
5
2
4
4
)
=
1
7
4
8
. The only factor of
1
7
4
8
that has four digits is
1
7
4
8
itself. Since
5
8
4
1
÷
1
7
4
8
=
3
.
.
.
5
9
7
,
r
=
5
9
7
.
∴
2
x
−
3
r
=
2
×
1
7
4
8
−
3
×
5
9
7
=
3
4
9
6
−
1
7
9
1
=
5
9
6
.
1 1 0 8 5 ≡ 9 3 3 7 ≡ 5 8 4 1 ≡ r ( m o d x )
Now, 1 1 0 8 5 − 9 3 3 7 ≡ 1 7 4 8 ≡ r − r ≡ 0 ≡ x ( m o d x ) ⇒ 1 7 4 8 ≡ x ( m o d x )
This implies that 1748 is a multiple of x. Hence, x is a factor of 1748.
x ϵ 1 , 2 , 4 , 1 9 , 2 3 , 3 8 , 4 6 , 7 6 , 9 2 , 4 3 7 , 8 7 4 , 1 7 4 8 (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.
1 1 0 8 5 ≡ 9 3 3 7 ≡ 5 8 4 1 ≡ 5 9 7 ( m o d 1 7 4 8 )
∴ r = 5 9 7 , x = 1 7 4 8 , 2 x − 3 r = 3 4 9 6 − 1 7 9 1 = 1 7 0 5
Below is a different approach, in Python:
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 |
|
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
I figured that x will be less than or equal to 9337 - 5841 and put it in my program:
1 2 3 4 5 |
|
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= 1 7 0 5
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.
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
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 : = 5 8 4 1 , b : = 9 3 3 7 , c : = 1 1 0 8 5 and now the question above can be formulated as a b c ∴ a ≡ b ≡ c ≡ r m o d x ≡ r m o d x ≡ r m o d x ≡ r m o d x . We make use of the rule that if c ≡ r m o d x and b ≡ r m o d x , then c − b ≡ r − r ≡ 0 m o d x and thus c − b = 1 7 4 8 ≡ 0 m o d x . Now although x = 8 7 4 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 and c . This means that x = 1 7 4 8 and all that's left to do is find out r which will be done using a : 5 8 4 1 = 3 ⋅ 1 7 4 8 + 5 9 7 ⟹ r = 5 9 7 . Now simply plug in 2 ⋅ 1 7 4 8 − 3 ⋅ 5 9 7 = 1 7 0 5 .
l e t a , b , c ∈ N : a x = 5 8 4 1 − r . . . . . . . . . . [ 1 ] b x = 9 3 3 7 − r . . . . . . . . . . [ 2 ] c x = 1 1 0 8 5 − r . . . . . . . . . . [ 3 ] [ 2 ] − [ 1 ] ⇒ ( b − a ) x = 3 4 9 6 [ 3 ] − [ 2 ] ⇒ ( c − b ) x = 1 7 4 8 ∵ g cd ( 3 4 9 6 , 1 7 4 8 ) = 1 7 4 8 ∴ g cd ( ( c − b ) x , ( b − a ) x ) ∵ x i s a c o m m o n f a c t o r o f 3 9 4 6 a n d 1 7 4 8 ∴ x ∣ 1 7 4 8 ⇒ x ∈ { 1 7 4 8 , 8 7 4 , 4 3 7 , 9 2 , 7 6 , 4 6 , 3 8 , 2 3 , 1 9 , 4 , 2 , 1 } ∵ x i s 4 a d i g i t n u m b e r ∴ x = 1 7 4 8 [ 1 ] ⇒ r = 5 9 7 ⇒ 2 x − 3 = 2 × 1 7 4 8 − 3 × 5 9 7 = 3 4 9 6 − 1 7 9 1 = 1 7 0 5
Since 9 3 3 7 − 5 8 4 1 = 3 4 9 6 , 1 1 0 8 5 − 9 3 3 7 = 1 7 4 8 , and 3 4 9 6 = 1 7 4 8 × 2 , x could probably be 1 7 4 8 . If x = 1 7 4 8 , r = 5 9 7 , which works for 5 8 4 1 , 9 3 3 7 , and 1 1 0 8 5 . So 2 x − 3 r = ( 2 × 1 7 4 8 ) − ( 3 × 5 9 7 ) = 3 4 9 6 − 1 7 9 1 = 1 7 0 5
x needs to be a factor of 1748. Since it needs to be a 4-digit number, x must be 1748.
⟹ ⟹ ⟹ ⟹ ⟹ For 0 ≤ r < x 5 8 4 1 = a x + r 9 3 3 7 = b x + r 1 1 0 8 5 = c x + r ( c − b ) x = 1 7 4 8 x ∣ 1 7 4 8 Since x is a four digit number x = 1 7 4 8 Now, 5 8 4 1 = 1 7 4 8 × 3 + 5 9 7 r = 5 9 7 2 x − 3 r = 1 7 0 5
Problem Loading...
Note Loading...
Set Loading...
I will post most common solution after a few solutions have been posted.