1 9 7 4 3 < β α < 7 7 1 7
Let α and β be positive integers that satisfy the inequality above. Find the minimum possible value of β .
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.
The left continued fraction is [ 0 , 4 , 1 , 1 , 1 8 / 7 ] . The right continued fraction is [ 0 , 4 , 1 , 1 , 8 ] . So the fractions in between it are of the form [ 0 , 4 , 1 , 1 , x ] for some x between 1 8 / 7 and 8 . That is, we have β α = 9 x + 5 2 x + 1 for some rational x between 1 8 / 7 and 8 . (I guess I could have gotten to that last sentence without continued fractions, now that I look at it.)
Let x = p / q with p and q positive coprime integers. Then β = 9 p + 5 q (exercise: 2 p + q and 9 p + 5 q are relatively prime!), and this is what we want to minimize. It's clear that p = 3 , q = 1 , β = 3 2 is best possible, since for all other p / q > 1 8 / 7 , p has to be at least 4 and that's already too big.
43B/197 <A<17B/77 So 43B/197 +m/197=17B/77-t/77 Giving 38B=77m +197t 38 divides 77m+197t implies 38 divides m+7t So m+7t =38 and 77m+197t=38B =2926-342t So B=77-9t and as t<or=5 B is min. when t=5 So min. B =32
Can you please elaborate "continued fraction " with respect to this problem ? Thanks.
Solve Diophantine equations, 197x-43y>0, 17y-77x>0, using wolfram alpha. You get ( x/y) = (7/32), (9/41), (11/50), (13/59), (15/68), (19/87) and (31/142) as possible pairs. Thus, choosing the lowest pair (7/32) gives answer = 32.
If a, b, c and d are positive and b a < d c , then b a < b + d a + c < d c .
This means that:
1 9 7 4 3 = 1 9 7 y 4 3 y < 1 9 7 y + 7 7 x 4 3 y + 1 7 x < 7 7 x 1 7 x = 7 7 1 7 , where x and y are positive integers.
β α = 1 9 7 y + 7 7 x 4 3 y + 1 7 x WLOG we can assume that g cd ( x , y ) = 1 .
g cd ( ( 4 3 y + 1 7 x ) , ( 1 9 7 y + 7 7 x ) ) = k
g cd ( k , x ) = 1 or g cd ( k , y ) = 1 or both. If this wasn't true, then k would have to divide both 1 7 ( x + y ) and 7 7 ( x + y ) , which means dividing both 77 and 17.
k ∣ 4 3 ( 1 9 7 y + 7 7 x ) − 1 9 7 ( 4 3 y + 1 7 x ) and k ∣ 1 7 ( 1 9 7 y + 7 7 x ) − 7 7 ( 4 3 y + 1 7 x ) , which means k ∣ 3 8 .
If we assume k = 3 8 , we must find the smallest possible positive integer pair ( x , y ) such that 3 8 ∣ ( 1 7 x + 4 3 y ) and 3 8 ∣ ( 7 7 x + 1 9 7 y ) , which is ( 3 , 5 ) .
If we assume k = 1 9 , the smallest possible integer pair that satisfies 1 9 ∣ ( 1 7 x + 4 3 y ) and 1 9 ∣ ( 7 7 x + 1 9 7 y ) is ( 2 , 5 ) .
Correct solution (the one which produces smaller β ) is ( x , y ) = ( 3 , 5 )
a = 1 9 7 4 3 = . 2 1 8 2 7 4 , . . . . b = 7 7 1 7 = . 2 2 0 7 7 9 , . . . . . . c = a + b 2 = 4 . 5 6 I f β α o < a , a n d β + 1 α o > b T h e n α > α o . M i n β , α a l s o i s m i n . A s s u m e α o , t r y β = α o ∗ c . S t a r t w i t h α o = 1 0 ( S i n c e 1 7 i s i n b ) α o = 1 0 , β = 1 0 ∗ c = 4 5 . 6 s a y 4 5 , β α o = . 2 2 2 2 > b . α o = 8 , β = 8 ∗ c = 3 6 . 5 s a y 3 7 , β α o = . 2 1 6 < a . α o = 7 , β = 7 ∗ c = 3 1 . 9 s a y 3 2 , β α o = . 2 1 8 7 5 6 b e t w e e n a a n d b . v e r y n e a r a a n d l e s s t h a n b . s o t r y β = 3 3 . β α o = . 2 1 2 1 2 1 < a . 3 2 a g o o d c a n d i d a t e . S e e i f α o = 6 i s p o s s i b l e . α o = 6 , β = 6 ∗ c = 2 7 . 4 s a y 2 8 , β α o = . 2 2 1 4 > b . s o β = 2 9 g i v e β α o = . 2 0 7 < a . N o v a l u e b e t w e e n a a n d b . S o 7 a n d 3 2 i s m i n i m u m . F o r a n α if there is no value between a and b , go to higher value. I f t h e f i r s t v a l u e w a s 4 5 1 0 t a k e n o w K ∗ 4 5 K ∗ 1 0 W h e r e K = 1 , 2 , 3 , 4 , . . . .
Problem Loading...
Note Loading...
Set Loading...
From β α < 7 7 1 7 . We note that α = ⌊ 7 7 1 7 β ⌋ will satisfy the upper limit condition, when β < 7 7 . Our task is the find the β < 7 7 such that β ⌊ 7 7 1 7 β ⌋ > 1 9 7 4 3 that is satisfying the lower limit condition, ⇒ ⌊ 7 7 1 7 β ⌋ > 1 9 7 4 3 β .
Let us now check the minimum β , when ⌊ 7 7 1 7 β ⌋ = 1 , 2 , 3 , . . . and check if the condition ⌊ 7 7 1 7 β ⌋ > 1 9 7 4 3 β is met.
\(\begin{array} {} \lfloor \frac {17}{77} \beta \rfloor = 1 & \Rightarrow \beta = 5 & \Rightarrow \frac{43}{197} \beta = 1.091 \color{red}{>} 1 \\ \lfloor \frac {17}{77} \beta \rfloor = 2 & \Rightarrow \beta = 10 & \Rightarrow \frac{43}{197} \beta = 2.182 \color{red}{>} 2 \\ \lfloor \frac {17}{77} \beta \rfloor = 3 & \Rightarrow \beta = 14 & \Rightarrow \frac{43}{197} \beta = 3.055 \color{red}{>} 3 \\ \lfloor \frac {17}{77} \beta \rfloor = 4 & \Rightarrow \beta = 19 & \Rightarrow \frac{43}{197} \beta = 4.147 \color{red}{>} 4 \\ \lfloor \frac {17}{77} \beta \rfloor = 5 & \Rightarrow \beta = 23 & \Rightarrow \frac{43}{197} \beta = 5.020 \color{red}{>} 5 \\ \lfloor \frac {17}{77} \beta \rfloor = 6 & \Rightarrow \beta = 28 & \Rightarrow \frac{43}{197} \beta = 6.111 \color{red}{>} 6 \\ \lfloor \frac {17}{77} \beta \rfloor = 7 & \Rightarrow \beta = 32 & \Rightarrow \frac{43}{197} \beta = 6.984 \color{blue}{<} 7 \end{array} \)
Therefore the minimum possible value of β = 3 2 .