Simple divibility problem

Number Theory Level 3

If a , b , c a,b,c are integers such that 7 a + 4 b − 3 c = 0 7a+4b-3c=0 , then ( a + b ) ( b + c ) ( c + a ) (a+b)(b+c)(c+a) is divisible by which largest factor below?

21 42 84 14

ChengYiin Ong by ChengYiin Ong , 17, Malaysia

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.

2 solutions

ChengYiin Ong
Jul 24, 2019

By using modulo congruence, 7 a + 4 b ≡ 0 ( m o d 3 ) ⇒ a + b ≡ 0 ( m o d 3 ) 7a+4b \equiv 0 (mod 3) \Rightarrow a+b \equiv 0 (mod 3)

Rearranging the expressions, c = 7 a + 4 b 3 c=\frac{7a+4b}{3} ⇒ ( a + b ) ( b + c ) ( c + a ) = ( a + b ) 7 3 ( a + b ) 2 3 ( 5 a + 2 b ) \Rightarrow (a+b)(b+c)(c+a)=(a+b)\frac{7}{3}(a+b)\frac{2}{3}(5a+2b)

We also know that 5 a + 2 b ≡ 0 ( m o d 3 ) 5a+2b \equiv 0 (mod3)

Let a + b = 3 k a+b=3k and 5 a + 2 b = 3 j 5a+2b=3j , then ( a + b ) ( b + c ) ( c + a ) = ( 3 k ) 7 3 ( 3 k ) 2 3 ( 3 j ) = 42 k 2 j (a+b)(b+c)(c+a)=(3k)\frac{7}{3}(3k)\frac{2}{3}(3j)=42k^2j

Thus, 42 ∣ ( a + b ) ( b + c ) ( c + a ) 42|(a+b)(b+c)(c+a) .

2 Helpful 0 Interesting 0 Brilliant 0 Confused

What about the solution (2,1,6): 2 * 7+1 * 4-3 * 6=14+4-18=0 confirmed. (2+1) * (6+1) * (6+2)=3 * 7 * 8=21 * 8=84 * 2 Meaning 84 should be the largest factor, doesnt it?

Eric Scholz - 1 year, 10 months ago

Log in to reply

Since 7 ( a + b ) = 3 ( b + c ) 7(a+b)=3(b+c) , we have a + b a+b divisible by 3 3 and b + c b+c divisible by 7 7 . Since 7 ( a + c ) = 2 ( 5 c − b ) 7(a+c) = 2(5c-b) we have a + c a+c divisible by 2 2 . Thus ( a + b ) ( a + c ) ( b + c ) (a+b)(a+c)(b+c) is always divisible by 42 42 .

We want the largest possible integer N N such that N N always divides ( a + b ) ( a + c ) ( b + c ) (a+b)(a+c)(b+c) . From what we have already shown, N N must be a multiple of 42 42 . The case a = 3 , b = 0 , c = 7 a=3,b=0,c=7 gives ( a + b ) ( a + c ) ( b + c ) = 210 (a+b)(a+c)(b+c)=210 , and so N N divides 210 = 42 × 5 210 = 42\times5 . On the other hand, the case a = 0 , b = 3 , c = 4 a=0,b=3,c=4 gives ( a + b ) ( a + c ) ( b + c ) = 84 (a+b)(a+c)(b+c)=84 , and hence N N divides 84 = 42 × 2 84 = 42\times2 . These three facts about N N tell us that N = 42 N=42 .

Mark Hennings - 1 year, 10 months ago

I believe this is from OMK 2019?

Bryan Lee Shi Yang - 1 year, 8 months ago

Log in to reply

Yes I am also competing in it.

ChengYiin Ong - 1 year, 8 months ago

Solve [ 7 a + 4 b − 3 c = 0 , a ] ⇒ a → 1 7 ( 3 c − 4 b ) \text{Solve}[7 a+4 b-3 c=0,a] \Rightarrow a\to \frac{1}{7} (3 c-4 b)

( a + b ) ( a + c ) ( b + c ) /. a → 1 7 ( 3 c − 4 b ) ⇒ 1 49 ( − 6 ) ( 2 b − 5 c ) ( b + c ) 2 (a+b) (a+c) (b+c)\text{/.}\,a\to \frac{1}{7} (3 c-4 b) \Rightarrow \frac{1}{49} (-6) (2 b-5 c) (b+c)^2

GCD@@Union [ Flatten [ Table [ If [ 1 7 ( 3 c − 4 b ) ∈ Z , 1 49 ( − 6 ) ( 2 b − 5 c ) ( b + c ) 2 , Nothing ] , { b , 0 , 6 } , { c , 0 , 6 } ] ] ] ⇒ 42 \text{GCD}\text{@@}\text{Union}\left[\text{Flatten}\left[\text{Table}\left[\text{If}\left[\frac{1}{7} (3 c-4 b)\in \mathbb{Z},\frac{1}{49} (-6) (2 b-5 c) (b+c)^2,\text{Nothing}\right],\{b,0,6\},\{c,0,6\}\right]\right]\right] \Rightarrow 42

0 Helpful 0 Interesting 0 Brilliant 1 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...