As x ranges over all positive integers, what is the smallest positive integer value of
2 4 7 x 2 + 3 ?
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.
Great job! Very carefully written and complete solution!
Can anyone suggest some text / video on internet regarding arithmetic modulus and Chinese Remainder Theorem. I always have some difficulty reaching the answer in these type of problems.
Log in to reply
The wikipedia page http://en.wikipedia.org/wiki/Chinese remainder theorem is actually quite readable, but I am sure that others may suggest better sources.
The CRT tells you that if m , n are coprime, and we have x = a m o d m and x = b m o d n , then there is a unique solution x m o d ( m n ) .
How to actually find that solution isn't strictly part of the theorem, although programs to do it are sometimes called "Chinese remainder theorem calculators". The Wikipedia page has an overview of some algorithms. Learning the Extended Euclidean Algorithm is a good idea,. it's something you can do easily on paper.
I am a newbie at Math Olympiads here and I need some help haha
"Using the Chinese Remainder Theorem, we find the following: x≡−6(mod13) and x≡−4(mod19) ⇝x≡ 72(mod247) x≡+6(mod13) and x≡−4(mod19) ⇝x≡110(mod247) x≡−6(mod13) and x≡+4(mod19) ⇝x≡137(mod247) x≡+6(mod13) and x≡+4(mod19) ⇝x≡175(mod247)"
Mind doing a little explanation?
I am new to congruences so can you please tell me that... "We use chinese remainder theorem when the modulo are relatively prime, but here we have 4 congruences for x, in which 2 pairs are not relatively prime, so can you please explain me how did you solve after--->"
Therefore, we must have x ≡ ± 6 ( m o d 1 3 ) and x ≡ . ± 4 ( m o d 1 9 )
can u solve this with using any theorms .....?
Log in to reply
I solved it without using theorems, reducing the cases and deducting which form must the integers have, althought I don't think this could be called a solution, and I was luck because the answer was a small number.
It's just Chinese Remainder Theorem
We only need to find the smallest integer that x 2 ≡ x 2 ≡ 1 0 m o d 1 3 1 6 m o d 1 9 Refer to Quadratic Residues - Primes , we know that
x = x = 1 3 k + 6 or x = 1 3 k + 7 1 9 k + 4 or x = 1 9 k + 1 5
Solving them by the Chinese Remainder Theorem , we have x = 7 2 , 1 1 0 , 1 3 7 , 1 7 5 . So x = 7 2 , which gives ( x 2 + 3 ) / 2 4 7 = 2 1 .
Nicely done!
Typo: Refer → Referring
I think this is the same as @JimmyK 's answer
Nice job! Yes, this is basically the same as Jimmy K.'s solution.
Note that 2 4 7 = 1 3 ⋅ 1 9 , hence we need 1 3 ∣ x 2 + 3 and 1 9 ∣ x 2 + 3 , i.e. { x 2 ≡ 1 0 ( m o d 1 3 ) x 2 ≡ 1 6 ( m o d 1 9 ) Examining quadratic residues modulos 1 3 , 1 9 we find that it's equivalent to { x ≡ ⟨ 6 , 7 ⟩ ( m o d 1 3 ) x ≡ ⟨ 4 , 1 5 ⟩ ( m o d 1 9 ) where the notation ⟨ a , b ⟩ denotes exactly one of a , b (this is not standard notation). Hence there exists a ∈ N ∪ { 0 } such that x = 1 9 a + ⟨ 4 , 1 5 ⟩ So in first congruence 6 a ≡ ⟨ 6 , 7 ⟩ − ⟨ 4 , 1 5 ⟩ ( m o d 1 3 ) i.e. a ≡ 6 ⟨ 6 , 7 ⟩ − ⟨ 4 , 1 5 ⟩ ≡ ( − 2 ) ⋅ ( ⟨ 6 , 7 ⟩ − ⟨ 4 , 1 5 ⟩ ) ( m o d 1 3 ) where the fraction doesn't denote actual division by 6 , but modular multiplicative inverse of 6 in modulo 1 3 .
1) ⟨ 4 , 1 5 ⟩ = 4 and ⟨ 6 , 7 ⟩ = 6 , then a ≡ ( − 2 ) ⋅ 2 ≡ 9 ( m o d 1 3 ) . So there exists b ∈ N ∪ { 0 } such that a = 1 3 b + 9 , i.e. x = 2 4 7 b + 1 7 5 .
2) ⟨ 4 , 1 5 ⟩ = 1 5 and ⟨ 6 , 7 ⟩ = 6 , then a ≡ ( − 2 ) ⋅ ( − 9 ) ≡ 5 ( m o d 1 3 ) . So there exists b ∈ N ∪ { 0 } such that a = 1 3 b + 5 , i.e. x = 2 4 7 b + 1 1 0 .
3) ⟨ 4 , 1 5 ⟩ = 4 and ⟨ 6 , 7 ⟩ = 7 , then a ≡ ( − 2 ) ⋅ 3 ≡ 7 ( m o d 1 3 ) . So there exists b ∈ N ∪ { 0 } such that a = 1 3 b + 7 , i.e. x = 2 4 7 b + 1 3 7 .
4) ⟨ 4 , 1 5 ⟩ = 1 5 and ⟨ 6 , 7 ⟩ = 7 , then a ≡ ( − 2 ) ⋅ ( − 8 ) ≡ 3 ( m o d 1 3 ) . So there exists b ∈ N ∪ { 0 } such that a = 1 3 b + 3 , i.e. x = 2 4 7 b + 7 2 .
Hence all x ∈ N such that 2 4 7 ∣ x 2 + 3 are x ∈ { 2 4 7 b + c ∣ b ∈ N ∪ { 0 } ∧ c ∈ { 7 2 , 1 1 0 , 1 3 7 , 1 7 5 } } It's obvious that smallest 2 4 7 x 2 + 3 will have smallest x and smallest x is 7 2 , hence the value sought is 2 4 7 7 2 2 + 3 = 2 1
Great job!
Nicely done!
I whipped up a quick little C program to help me here:
int i = 0, num = 1.5, answer = 1;
do { num = ( i * i + 3 );
i += 1;
answer = num/247;
}
while ( num % 247 != 0 );
printf("%i\n", answer);
THIS IS NOT A PROGRAMMING PROBLEM!!!!!
Though you got the answer, this is not the solution. I guess Chinese Remainder Theorem is only mathematical answer here.
Hahahaha, i did the very same using python. It wouldnt work though.
2 4 7 x 2 + 3 = k ⇔ x 2 + 3 = 1 3 ⋅ 1 9 k
⇒ when x 2 is divided by 1 3 , the remainder is 1 0
⇒ [ x = 1 3 a + 6 x = 1 3 a + 7 ,
Similarly, we also have ⇒ [ x = 1 9 b + 4 x = 1 9 b + 1 5 .
Case 1: x = 1 3 a + 6 = 1 9 b + 4
⇒ a = 1 3 1 9 b − 2 = b + 1 3 6 b − 2 ,
set p = 1 3 6 b − 2 ⇒ b = 6 1 3 p + 2 = 2 p + 6 p + 2 ,
set t = 6 p + 2 ⇒ p = 6 t − 2 ,
hence b = 1 3 t − 4 , a = 1 9 t − 6 , x = 2 4 7 t − 7 2 ,
therefore, the smallest of x 2 in this case is 1 7 5 2 .
Similarly, in 3 remaining cases, we have:
Case 2: x = 1 3 a + 6 = 1 9 b + 1 5
x = 2 4 7 t + 3 5 7 ⇒ x m i n 2 = 1 1 0 2 .
Case 3: x = 1 3 a + 7 = 1 9 b + 4
x = 2 4 7 t − 1 1 0 ⇒ x m i n 2 = 1 3 7 2 .
Case 4: x = 1 3 a + 7 = 1 9 b + 1 5
x = 2 4 7 t + 3 1 9 ⇒ x m i n 2 = 7 2 2 .
The positive integer value of k is the smallest if and only if the positive integer value of x 2 .
Besides, basing on 4 above cases we have the smallest positive integer value of x 2 is 7 2 2 ,
so k m i n = 2 4 7 7 2 2 + 3 = 2 1 .
Great job!
Since 2 4 7 = 1 3 ⋅ 1 9 , the problem is equivalent to solve the congruence equations: x 2 ≡ − 3 ( m o d 1 3 ) and x 2 ≡ − 3 ( m o d 1 9 ) . By Lagrange's theorem, each of the congruence has at most two solutions. Also note that if x 0 is a solution to the congruence x 2 ≡ a ( m o d p ) , then p − x 0 is also a solution to the congruence. In our case we can check very easily that x ≡ 6 , 7 ( m o d 1 3 ) for the first congruence and x ≡ 4 , 1 5 ( m o d 1 9 ) for the second congruence. We then solve the four systems of linear congruence equations:
case I x ≡ 6 ( m o d 1 3 ) and x ≡ 4 ( m o d 1 9 ) . The first congruence yields x = 1 3 k + 6 for some integer k . Substituting into the second congruence, we have 1 3 k ≡ − 2 ( m o d 1 9 ) . Multiplying by 3 on both sides yields k ≡ − 6 ≡ 1 3 ( m o d 1 9 ) . This implies k = 1 9 ℓ + 1 3 for some integer ℓ . Hence x = 1 3 ( 1 9 ℓ + 1 3 ) + 6 = 2 4 7 ℓ + 1 7 5 or x ≡ 1 7 5 ( m o d 2 4 7 ) .
case II x ≡ 6 ( m o d 1 3 ) and x ≡ 1 5 ( m o d 1 9 ) . By a similar argument as in case I, we get x ≡ 1 1 0 ( m o d 2 4 7 ) .
case III x ≡ 7 ( m o d 1 3 ) and x ≡ 4 ( m o d 1 9 ) . By a similar argument as in case I, we get x ≡ 1 3 7 ( m o d 2 4 7 ) .
case IV x ≡ 7 ( m o d 1 3 ) and x ≡ 1 5 ( m o d 1 9 ) . By a similar argument as in case I, we get x ≡ 7 2 ( m o d 2 4 7 ) .
We conclude that the smallest positive integer x such that ( x 2 + 3 ) / 2 4 7 is an integer is x = 7 2 . This value of x also yields the smallest integral value of ( x 2 + 3 ) / 2 4 7 since x 2 + 3 is positive. This is ( 7 2 2 + 3 ) / 2 4 7 = 2 1 .
Great job!
x^{2}=247k-3 x^{2}-16=13 19 k-19 (x+4)(x-4)=19(13 k-1) As 19 is a prime so, 19|x+4 or 19|x-4 x=19m-4 or x=19m+4 as output should be minimum putting x=19m-4 we get 361 m^{2}-152 m +19/247 =19(19 m^{2}-8 m+1)/13 19 =19 m^{2}-8 m+1/13 13m^{2}/13 -13*m/13 +(6m^{2}+5m+1)/13 after factorising we get (2m+1)(3m+1)/13 minimum of m is =4 so, x=72 and answwr is 21
The smallest value will come when x=72 So, by putting x=72 in the equation, the answer becomes 21
i wrote all the multiples of 247. The multiple should be in such a way on subtracting 3 from it, it should be a perfect square number 247*21=5187. 5187-3=5184 whose square root is 72(positive integer)
Make equation as [(247*x)-3]^(1/2) solution to this must be integer
put x=72,,, so we get 21 as the least positve integer for the above equation .
The smallest value will come when
x=72
So, by putting x=72 in the equation,
the answer becomes 21
ow u the getting the x=the72?how?tells me plz
Problem Loading...
Note Loading...
Set Loading...
Suppose 2 4 7 x 2 + 3 is an integer. Then, x 2 ≡ − 3 ( m o d 2 4 7 ) .
Since 2 4 7 = 1 3 ⋅ 1 9 , by the Chinese Remainder Theorem, x 2 ≡ − 3 ≡ 1 0 ( m o d 1 3 ) and x 2 ≡ − 3 ≡ 1 6 ( m o d 1 9 ) .
In ( mod 1 3 ) , we have 0 2 ≡ 0 , ( ± 1 ) 2 ≡ 1 , ( ± 2 ) 2 ≡ 4 , ( ± 3 ) 2 ≡ 9 , ( ± 4 ) 2 ≡ 3 , ( ± 5 ) 2 ≡ 1 2 , ( ± 6 ) 2 ≡ 1 0 .
In ( mod 1 9 ) , we have 0 2 ≡ 0 , ( ± 1 ) 2 ≡ 1 , ( ± 2 ) 2 ≡ 4 , ( ± 3 ) 2 ≡ 9 , ( ± 4 ) 2 ≡ 1 6 , ( ± 5 ) 2 ≡ 6 , ( ± 6 ) 2 ≡ 1 7 , ( ± 7 ) 2 ≡ 1 1 , ( ± 8 ) 2 ≡ 7 , ( ± 9 ) 2 ≡ 5 .
Therefore, we must have x ≡ ± 6 ( m o d 1 3 ) and x ≡ ± 4 ( m o d 1 9 ) .
Using the Chinese Remainder Theorem, we find the following: x ≡ − 6 ( m o d 1 3 ) and x ≡ − 4 ( m o d 1 9 ) ⇝ x ≡ 7 2 ( m o d 2 4 7 ) x ≡ + 6 ( m o d 1 3 ) and x ≡ − 4 ( m o d 1 9 ) ⇝ x ≡ 1 1 0 ( m o d 2 4 7 ) x ≡ − 6 ( m o d 1 3 ) and x ≡ + 4 ( m o d 1 9 ) ⇝ x ≡ 1 3 7 ( m o d 2 4 7 ) x ≡ + 6 ( m o d 1 3 ) and x ≡ + 4 ( m o d 1 9 ) ⇝ x ≡ 1 7 5 ( m o d 2 4 7 )
Therefore, we must have x ≡ 7 2 , 1 1 0 , 1 3 7 , 1 7 5 ( m o d 2 4 7 ) .
Since 2 4 7 x 2 + 3 is positive and increasing for x > 0 , the smallest positive integer value of 2 4 7 x 2 + 3 is attained by the smallest positive integer x such that 2 4 7 x 2 + 3 is an integer, i.e. x = 7 2 . This gives 2 4 7 x 2 + 3 = 2 4 7 7 2 2 + 3 = 2 1 .