Consecutive integers

Number Theory Level 4

Let $a < b < c < d$ be four consecutive positive integers such that

$a$ is divisible by 5,
$b$ is divisible by 7,
$c$ is divisible by 9, and
$d$ is divisible by 11.

Find the minimum value of $a+b+c+d.$

The answer is 6946.

5 solutions

Calvin Lin Staff
May 21, 2016

Relevant wiki: Modular Arithmetic - Word Problems

We are told that $a \equiv 0 \pmod{5}, a \equiv -1 \pmod{7}, a \equiv -2 \pmod{9}, a \equiv -3 \pmod{11}$ .

Hence, $2a-5 \equiv 0 \pmod{5, 7, 9, 11}$ which gives us $2a \equiv 5 \pmod{3465}$ and hence $a \equiv 5 \times 1733 \equiv 1735 \pmod{3465}$ .

Note: This works out nicely because I'm exploiting the arithmetic progression of the modulus. In general, it's not that nice and this one-step solution would unlikely work.

Very clever indeed! (+1)

Otto Bretscher - 5 years ago

but how to get 2a-5?

first last - 5 months, 2 weeks ago

Otto Bretscher
May 20, 2016

A quick survey shows that the first two properties are satisfied by $a=20+35k$ , the first three by $a=160+315k$ , and all of them by $1735+3465k$ . The answer is $\boxed{6946}$

sir ca you please tell how have you got the first three prooperties i.e a=160 +315k

Deepansh Jindal - 5 years ago

Sure!

Starting from $a=5k$ , we are solving a congruency at each stage where we look for the smallest positive solution $k$ . Since the numbers we are dealing with are small, we can do this by inspection. Now

$b=a+1=5k+1\equiv 0 \pmod{7}$ for $k=4$ so that $a=5\times 4=20$ is the smallest solution

$c=a+2=22+5\times 7 k\equiv 4-k\equiv 0 \pmod{9}$ for $k=4$ so that $a=20+35\times 4=160$ is the smallest solution.

$d=a+3=163+5\times 7\times 9k\equiv 9+7k \equiv 0 \pmod{11}$ for $k=5$ so $a=160+315\times 5=1735$

I hope this helps.

Otto Bretscher - 5 years ago

sir can you please help me over the second and third step .. how have you tranformed c=a+2 = 22+5 7k congruent to 4-k and d= a+3 =163+5 7*9k congruent 9 +7k ..... sir please help me i am struggling on these transformation

Deepansh Jindal - 5 years ago

@Deepansh Jindal – $22\equiv 4 \pmod{9}$ just means that $22-4=18$ is divisible by $9$ . By the same tokenm $5\times 7k=35k \equiv -k \pmod 9$ means that $36k$ is divisible by $9$ . Now see whether you can understand the other congruences!

Otto Bretscher - 5 years ago

@Otto Bretscher – thanks a lot sir got it and a brilliant solution sir .... again thanks sir for your help

Deepansh Jindal - 5 years ago

@Deepansh Jindal – My pleasure...

Otto Bretscher - 5 years ago

How did you came to the conclusion, that c = 22 + 35k ?

Konstantin Zeis - 5 years ago

@Konstantin Zeis – In the previous step we find that $a=20$ is the smallest solution modulo 5 and modulo 7. We get the other solutions if we add multiples of $7\times 5=35$ to 20. Thus $c=a+2$ must be of the form $22+35k$ .

I hope this makes sense.

Otto Bretscher - 5 years ago

Hi! My solution matches that of yours. But I wanted to know if there is any "extended " version of The Chinese Remainder Theorem that solves such congruences without trial and error. Thank you.

Shourya Pandey - 5 years ago

I would not call it "trial and error": it's a systematic process. Look at the extra explanation I gave in my response to Deepansh Jindal.

At some point in each step, we need to find a modular inverse, for example, the inverse of 7 modulo 11 in the last step. For larger numbers you might want to use the Euclidean algorithm to perform this step. In our example you would find $1=7\times 8- 5\times11$ , so that the inverse of 7 is 8 modulo 11.

Otto Bretscher - 5 years ago

Mr. Bretscher, How did you figure out that the answer was 6946? I was able to follow your work up to that last step, where you determined the minimum value of d . However, then I tried to substitute each of those values into the expression a + (a + 1) + (a + 2) + (a + 3). The solution I got was 5741.

John Taylor - 5 years ago

@John Taylor – I find $a=1735$ and the sum is $1735+1736+1737+1738=6946$

Otto Bretscher - 5 years ago

@Otto Bretscher – Thanks. Brain fart on my end. Also, can k can be set equal to 0? If so, why is this possible?

John Taylor - 5 years ago

Noureldin Yosri
May 21, 2016

the problem asks us to find x such that

$x \equiv 0 (mod 5) \\ x \equiv -1 (mod 7)\\ x \equiv -2 (mod 9)\\ x \equiv -3 (mod 11)\\$

as the bases (5,7,9,11) are pairwise coprime this problem becomes a direct application of CRT (Chinese Remainder Theorem) which states that x can be computed as

$B = \prod {base}_i = 3465\\ x = \sum_i a_i \times \frac{B}{{base}_i} \times [(\frac{B}{{base}_i})^{-1}]_{{base}_i}\\$

where $[y^{-1}]_a$ is the modular multiplicative inverse of y mod a which is equal to $y^{\phi(a) -1 } \% a$

applying this we get x = 1735 and the answer is x + (x + 1) + (x + 2) + (x + 3) = 4*x + 6 = 6946

Arjen Vreugdenhil
May 21, 2016

To get to small numbers as quickly as possible, I start with the last congruence, which yields $d = 11x.$ The other congruences reduce to $a = 11x - 3 \equiv x + 2 \equiv 0 \ \text{mod 5}; \\ b = 11x - 2 \equiv 4x + 5 \equiv 0\ \text{mod 7}\ \ \ \therefore\ \ \ x + 3 \equiv 0\ \text{mod 7}; \\ c = 11x - 1 \equiv 2x - 1\equiv 0\ \text{mod 9}\ \ \ \therefore\ \ \ x - 5 \equiv 0\ \text{mod 9}.$ Thus $x = 9y + 5,$ and $x + 2 = 9y + 7 \equiv 4y + 2\equiv 0\ \ \ \therefore\ \ \ y - 2\equiv 0\ \text{mod 5}; \\x + 3 = 9y + 8 \equiv 2y + 1\equiv 0\ \ \ \therefore\ \ \ y + 4\equiv 0\ \text{mod 7}.$ From the last equation we have $y \equiv 3$ mod 7, and we write $y = 7z + 3.$ Then $y - 2 = 7z + 1 \equiv 2z + 1 \equiv 0\ \text{mod 5},$ with the obvious smallest positive solution $z = 2$ . Thus $y = 7\cdot 2 + 3 = 17;\ \ \ \ x = 9\cdot 17 + 5 = 158;\ \ \ \ d = 11\cdot 158 = 1738.$ The answer is $1735 + 1736 + 1737 + 1738 = 4\cdot 1735 + 6 = 6946.$

Andreas Wendler
May 21, 2016

A small formula in EXCEL fulfills the purpose fast and comfortable...and the next task needn't wait long! ;-)

Consecutive integers

The answer is 6946.

5 solutions

0 pending reports