Not 1?

As x x ranges over all positive integers, what is the smallest positive integer value of

x 2 + 3 247 ? \frac{x^2 + 3} { 247}?


The answer is 21.

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.

12 solutions

Jimmy Kariznov
Sep 8, 2013

Suppose x 2 + 3 247 \tfrac{x^2+3}{247} is an integer. Then, x 2 3 ( m o d 247 ) x^2 \equiv -3 \pmod{247} .

Since 247 = 13 19 247 = 13 \cdot 19 , by the Chinese Remainder Theorem, x 2 3 10 ( m o d 13 ) x^2 \equiv -3 \equiv 10 \pmod{13} and x 2 3 16 ( m o d 19 ) x^2 \equiv -3 \equiv 16 \pmod{19} .

In ( mod 13 ) (\text{mod} \ 13) , we have 0 2 0 0^2 \equiv 0 , ( ± 1 ) 2 1 (\pm 1)^2 \equiv 1 , ( ± 2 ) 2 4 (\pm 2)^2 \equiv 4 , ( ± 3 ) 2 9 (\pm 3)^2 \equiv 9 , ( ± 4 ) 2 3 (\pm 4)^2 \equiv 3 , ( ± 5 ) 2 12 (\pm 5)^2 \equiv 12 , ( ± 6 ) 2 10 (\pm 6)^2 \equiv 10 .

In ( mod 19 ) (\text{mod} \ 19) , we have 0 2 0 0^2 \equiv 0 , ( ± 1 ) 2 1 (\pm 1)^2 \equiv 1 , ( ± 2 ) 2 4 (\pm 2)^2 \equiv 4 , ( ± 3 ) 2 9 (\pm 3)^2 \equiv 9 , ( ± 4 ) 2 16 (\pm 4)^2 \equiv 16 , ( ± 5 ) 2 6 (\pm 5)^2 \equiv 6 , ( ± 6 ) 2 17 (\pm 6)^2 \equiv 17 , ( ± 7 ) 2 11 (\pm 7)^2 \equiv 11 , ( ± 8 ) 2 7 (\pm 8)^2 \equiv 7 , ( ± 9 ) 2 5 (\pm 9)^2 \equiv 5 .

Therefore, we must have x ± 6 ( m o d 13 ) x \equiv \pm 6 \pmod{13} and x ± 4 ( m o d 19 ) x \equiv \pm 4 \pmod{19} .

Using the Chinese Remainder Theorem, we find the following: x 6 ( m o d 13 ) x \equiv -6 \pmod{13} and x 4 ( m o d 19 ) x \equiv -4 \pmod{19} x 72 ( m o d 247 ) \leadsto x \equiv \ \ 72 \pmod{247} x + 6 ( m o d 13 ) x \equiv +6 \pmod{13} and x 4 ( m o d 19 ) x \equiv -4 \pmod{19} x 110 ( m o d 247 ) \leadsto x \equiv 110 \pmod{247} x 6 ( m o d 13 ) x \equiv -6 \pmod{13} and x + 4 ( m o d 19 ) x \equiv +4 \pmod{19} x 137 ( m o d 247 ) \leadsto x \equiv 137 \pmod{247} x + 6 ( m o d 13 ) x \equiv +6 \pmod{13} and x + 4 ( m o d 19 ) x \equiv +4 \pmod{19} x 175 ( m o d 247 ) \leadsto x \equiv 175 \pmod{247}

Therefore, we must have x 72 x \equiv 72 , 110 110 , 137 137 , 175 ( m o d 247 ) 175 \pmod{247} .

Since x 2 + 3 247 \tfrac{x^2+3}{247} is positive and increasing for x > 0 x > 0 , the smallest positive integer value of x 2 + 3 247 \tfrac{x^2+3}{247} is attained by the smallest positive integer x x such that x 2 + 3 247 \tfrac{x^2+3}{247} is an integer, i.e. x = 72 x = 72 . This gives x 2 + 3 247 = 7 2 2 + 3 247 = 21 \tfrac{x^2+3}{247} = \tfrac{72^2+3}{247} = \boxed{21} .

Moderator note:

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.

Lokesh Sharma - 7 years, 9 months ago

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.

Alexander Borisov - 7 years, 9 months ago

The CRT tells you that if m , n m, n are coprime, and we have x = a m o d m x = a \mod m and x = b m o d n x = b \mod n , then there is a unique solution x m o d ( m n ) x \mod (mn) .

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.

Matt McNabb - 7 years, 9 months ago

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?

Tan Gian Yion - 7 years, 9 months ago

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 13 ) x \equiv \pm 6 \pmod{13} and x . ± 4 ( m o d 19 ) x \equiv .\pm 4 \pmod{19}

Adya Jaiswal - 7 years, 9 months ago

can u solve this with using any theorms .....?

Vineeth Naroju - 7 years, 9 months ago

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.

Jordi Bosch - 7 years, 9 months ago

It's just Chinese Remainder Theorem

Zi Song Yeoh - 7 years, 9 months ago
Ziyuan Lin
Sep 9, 2013

We only need to find the smallest integer that x 2 10 m o d 13 x 2 16 m o d 19 \begin{aligned} x^2\equiv& 10\mod{13}\\ x^2\equiv& 16\mod{19} \end{aligned} Refer to Quadratic Residues - Primes , we know that

x = 13 k + 6 or x = 13 k + 7 x = 19 k + 4 or x = 19 k + 15 \begin{aligned} x=&13k+6\mbox{ or }x=13k+7\\ x=&19k+4\mbox{ or }x=19k+15 \end{aligned}

Solving them by the Chinese Remainder Theorem , we have x = 72 , 110 , 137 , 175 x=72,110,137,175 . So x = 72 x=72 , which gives ( x 2 + 3 ) / 247 = 21 (x^2+3)/247=21 .

Moderator note:

Nicely done!

Typo: Refer → Referring

Ziyuan Lin - 7 years, 9 months ago

I think this is the same as @JimmyK 's answer

Ziyuan Lin - 7 years, 9 months ago

Nice job! Yes, this is basically the same as Jimmy K.'s solution.

Alexander Borisov - 7 years, 9 months ago
Jan J.
Sep 9, 2013

Note that 247 = 13 19 247 = 13 \cdot 19 , hence we need 13 x 2 + 3 13 \mid x^2 + 3 and 19 x 2 + 3 19 \mid x^2 + 3 , i.e. { x 2 10 ( m o d 13 ) x 2 16 ( m o d 19 ) \begin{cases} x^2 \equiv 10 \pmod{13} \\ x^2 \equiv 16 \pmod{19} \end{cases} Examining quadratic residues modulos 13 , 19 13,19 we find that it's equivalent to { x 6 , 7 ( m o d 13 ) x 4 , 15 ( m o d 19 ) \begin{cases} x \equiv \langle 6,7 \rangle \pmod{13} \\ x \equiv \langle 4,15 \rangle \pmod{19} \end{cases} where the notation a , b \langle a,b \rangle denotes exactly one of a , b a,b (this is not standard notation). Hence there exists a N { 0 } a \in \mathbb{N} \cup \{0\} such that x = 19 a + 4 , 15 x = 19a + \langle 4,15 \rangle So in first congruence 6 a 6 , 7 4 , 15 ( m o d 13 ) 6a \equiv \langle 6,7 \rangle - \langle 4,15\rangle \pmod{13} i.e. a 6 , 7 4 , 15 6 ( 2 ) ( 6 , 7 4 , 15 ) ( m o d 13 ) a \equiv \frac{\langle 6,7 \rangle - \langle 4,15\rangle}{6} \equiv (-2) \cdot \big(\langle 6,7 \rangle - \langle 4,15\rangle\big) \pmod{13} where the fraction doesn't denote actual division by 6 6 , but modular multiplicative inverse of 6 6 in modulo 13 13 .

1) 4 , 15 = 4 \langle 4,15 \rangle = 4 and 6 , 7 = 6 \langle 6,7 \rangle = 6 , then a ( 2 ) 2 9 ( m o d 13 ) a \equiv (-2) \cdot 2 \equiv 9 \pmod{13} . So there exists b N { 0 } b \in \mathbb{N} \cup \{0\} such that a = 13 b + 9 a = 13b + 9 , i.e. x = 247 b + 175 x = 247b + 175 .

2) 4 , 15 = 15 \langle 4,15 \rangle = 15 and 6 , 7 = 6 \langle 6,7 \rangle = 6 , then a ( 2 ) ( 9 ) 5 ( m o d 13 ) a \equiv (-2) \cdot (-9) \equiv 5 \pmod{13} . So there exists b N { 0 } b \in \mathbb{N} \cup \{0\} such that a = 13 b + 5 a = 13b + 5 , i.e. x = 247 b + 110 x = 247b + 110 .

3) 4 , 15 = 4 \langle 4,15 \rangle = 4 and 6 , 7 = 7 \langle 6,7 \rangle = 7 , then a ( 2 ) 3 7 ( m o d 13 ) a \equiv (-2) \cdot 3 \equiv 7 \pmod{13} . So there exists b N { 0 } b \in \mathbb{N} \cup \{0\} such that a = 13 b + 7 a = 13b + 7 , i.e. x = 247 b + 137 x = 247b + 137 .

4) 4 , 15 = 15 \langle 4,15 \rangle = 15 and 6 , 7 = 7 \langle 6,7 \rangle = 7 , then a ( 2 ) ( 8 ) 3 ( m o d 13 ) a \equiv (-2) \cdot (-8) \equiv 3 \pmod{13} . So there exists b N { 0 } b \in \mathbb{N} \cup \{0\} such that a = 13 b + 3 a = 13b + 3 , i.e. x = 247 b + 72 x = 247b + 72 .

Hence all x N x \in \mathbb{N} such that 247 x 2 + 3 247 \mid x^2 + 3 are x { 247 b + c b N { 0 } c { 72 , 110 , 137 , 175 } } x \in \Big\{247b + c \mid b \in \mathbb{N} \cup \{0\} \wedge c \in \{72,110,137,175\}\Big\} It's obvious that smallest x 2 + 3 247 \frac{x^2 + 3}{247} will have smallest x x and smallest x x is 72 72 , hence the value sought is 7 2 2 + 3 247 = 21 \frac{72^2 + 3}{247} = \boxed{21}

Moderator note:

Great job!

Nicely done!

Alexander Borisov - 7 years, 9 months ago
John B
Sep 8, 2013

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!!!!!

Zi Song Yeoh - 7 years, 9 months ago

Log in to reply

OK!!!!!

John B - 7 years, 9 months ago

Though you got the answer, this is not the solution. I guess Chinese Remainder Theorem is only mathematical answer here.

Mirza Baig - 7 years, 9 months ago

Log in to reply

Yes, indeed.

Alexander Borisov - 7 years, 9 months ago

Hahahaha, i did the very same using python. It wouldnt work though.

Júlio Cézar Mendes - 7 years, 6 months ago

x 2 + 3 247 = k x 2 + 3 = 13 19 k \frac{x^2+3}{247}=k\Leftrightarrow x^2+3=13\cdot 19k

\Rightarrow when x 2 x^2 is divided by 13 13 , the remainder is 10 10

[ x = 13 a + 6 x = 13 a + 7 , \Rightarrow \left[\begin{matrix}x=13a+6 \\ x=13a+7\end{matrix},\right.

Similarly, we also have [ x = 19 b + 4 x = 19 b + 15 . \Rightarrow \left[\begin{matrix}x=19b+4 \\ x=19b+15\end{matrix}.\right.

Case 1: x = 13 a + 6 = 19 b + 4 x=13a+6=19b+4

a = 19 b 2 13 = b + 6 b 2 13 \Rightarrow a=\frac{19b-2}{13}=b+\frac{6b-2}{13} ,

set p = 6 b 2 13 b = 13 p + 2 6 = 2 p + p + 2 6 p=\frac{6b-2}{13}\Rightarrow b=\frac{13p+2}{6}=2p+\frac{p+2}{6} ,

set t = p + 2 6 p = 6 t 2 t=\frac{p+2}{6}\Rightarrow p=6t-2 ,

hence b = 13 t 4 , a = 19 t 6 , x = 247 t 72 b=13t-4,a=19t-6,x=247t-72 ,

therefore, the smallest of x 2 x^2 in this case is 17 5 2 . 175^2.

Similarly, in 3 3 remaining cases, we have:

Case 2: x = 13 a + 6 = 19 b + 15 x=13a+6=19b+15

x = 247 t + 357 x m i n 2 = 11 0 2 . x=247t+357\Rightarrow x^2_{min}=110^2.

Case 3: x = 13 a + 7 = 19 b + 4 x=13a+7=19b+4

x = 247 t 110 x m i n 2 = 13 7 2 . x=247t-110\Rightarrow x^2_{min}=137^2.

Case 4: x = 13 a + 7 = 19 b + 15 x=13a+7=19b+15

x = 247 t + 319 x m i n 2 = 7 2 2 . x=247t+319\Rightarrow x^2_{min}=72^2.

The positive integer value of k k is the smallest if and only if the positive integer value of x 2 x^2 .

Besides, basing on 4 4 above cases we have the smallest positive integer value of x 2 x^2 is 7 2 2 72^2 ,

so k m i n = 7 2 2 + 3 247 = 21. k_{min}=\frac{72^2+3}{247}=21.

Great job!

Alexander Borisov - 7 years, 9 months ago

Since 247 = 13 19 , 247 = 13 \cdot 19, the problem is equivalent to solve the congruence equations: x 2 3 ( m o d 13 ) and x 2 3 ( m o d 19 ) . x^2 \equiv -3 \pmod{13} \quad \text{and} \quad x^2 \equiv -3 \pmod{19}. By Lagrange's theorem, each of the congruence has at most two solutions. Also note that if x 0 x_0 is a solution to the congruence x 2 a ( m o d p ) x^2\equiv a \pmod{p} , then p x 0 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 13 ) x\equiv 6, 7 \pmod{13} for the first congruence and x 4 , 15 ( m o d 19 ) x\equiv 4,15 \pmod{19} for the second congruence. We then solve the four systems of linear congruence equations:

case I \textbf{case I} x 6 ( m o d 13 ) x\equiv 6 \pmod{13} and x 4 ( m o d 19 ) . x\equiv 4 \pmod{19}. The first congruence yields x = 13 k + 6 x = 13k+6 for some integer k k . Substituting into the second congruence, we have 13 k 2 ( m o d 19 ) . 13k \equiv -2 \pmod{19}. Multiplying by 3 3 on both sides yields k 6 13 ( m o d 19 ) . k \equiv -6 \equiv 13 \pmod{19}. This implies k = 19 + 13 k =19 \ell + 13 for some integer . \ell. Hence x = 13 ( 19 + 13 ) + 6 = 247 + 175 or x 175 ( m o d 247 ) . x =13(19\ell+13)+6 = 247\ell + 175 \quad \text{or} \quad x\equiv 175 \pmod{247}.

case II \textbf{case II} x 6 ( m o d 13 ) x\equiv 6 \pmod{13} and x 15 ( m o d 19 ) . x\equiv 15 \pmod{19}. By a similar argument as in case I, we get x 110 ( m o d 247 ) . x\equiv 110 \pmod{247}.

case III \textbf{case III} x 7 ( m o d 13 ) x\equiv 7 \pmod{13} and x 4 ( m o d 19 ) . x\equiv 4 \pmod{19}. By a similar argument as in case I, we get x 137 ( m o d 247 ) . x\equiv 137 \pmod{247}.

case IV \textbf{case IV} x 7 ( m o d 13 ) x\equiv 7 \pmod{13} and x 15 ( m o d 19 ) . x\equiv 15 \pmod{19}. By a similar argument as in case I, we get x 72 ( m o d 247 ) . x\equiv 72 \pmod{247}.

We conclude that the smallest positive integer x x such that ( x 2 + 3 ) / 247 (x^2+3)/247 is an integer is x = 72. x=72. This value of x x also yields the smallest integral value of ( x 2 + 3 ) / 247 (x^2+3)/247 since x 2 + 3 x^2+3 is positive. This is ( 7 2 2 + 3 ) / 247 = 21 . (72^2+3)/247 =\boxed{ 21}.

Great job!

Alexander Borisov - 7 years, 9 months ago
Kushal Bose
Oct 29, 2015

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

Hadia Qadir
Sep 3, 2015

The smallest value will come when x=72 So, by putting x=72 in the equation, the answer becomes 21

P Patha
Nov 26, 2013

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)

Masoom Ali
Nov 26, 2013

Make equation as [(247*x)-3]^(1/2) solution to this must be integer

Hatim Khatir
Nov 8, 2013

put x=72,,, so we get 21 as the least positve integer for the above equation .

Arnav Shringi
Sep 11, 2013

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

Daniel Wang - 7 years, 9 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...