Find the number of coprime pairs ( a , b ) of positive integers subject to 0 < a < b < 1 0 1 0 0 , such that
a ∣ ( b 2 − 1 1 ) , b ∣ ( a 2 − 1 1 ) .
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.
Similar to one of my problems. Excellent problem/solution! I'm glad I saw root jumping almost immediately. Just one thing though. At first, I factored by difference of squares put my answer as 0 and then realized that was stupid (like, really stupid). I got it after all, and the system marked 582 correct, but in the solutions screen it says:
Correct answer: 582 Your answer: 0
Which isn't right. This is a bug.
Log in to reply
Same with my mine, but mine states 882
Thanks this is a bug for corrected problems, in which we do not display the correct answer that you typed. We will fix this in future.
You made a computation error when calculating w i . The recurrence is w i + 1 = 9 w i − w i − 1 , so the characteristic polynomial is t 2 − 9 t + 1 . The roots of this quadratic are t = 2 9 ± 7 7 .
Also, I get that v 2 3 8 ≈ 6 . 2 1 × 1 0 9 9 and v 2 3 9 ≈ 1 . 6 3 × 1 0 1 0 0 , so the largest v i < 1 0 1 0 0 is v 2 3 8 . Can you double-check?
Log in to reply
Thanks. I missed the discriminant by 1 and used 76 instead of 77. Fixed w i and t , with no changes to the rest.
You are right about v i . I forgot to account for the coefficient, and hence included an extra solution.
I've updated the answer to 582.
Log in to reply
Agreed that there are 2 3 8 u and v . Ah, I was off by 1 for a different reason: I was counting ( 1 , 1 ) . I guess I was lucky to get credit!
I write a python program to solve it (execute time: 0.4s)
import math
from fractions import gcd
test = 1
max_num = 10 ** 100
lstb = [1, 2, 5, 10, 7]
a = 2
b = 0
while a < max_num:
newa = a + 1
isSet = False
for tmp in lstb:
if tmp <= a:
continue
if not isSet:
newa = tmp
isSet = True
if tmp < newa:
newa = tmp
a = newa
a2 = a ** 2
foundB = False
for x in lstb :
if (a2 - 11) % x == 0:
candidate = (a2 - 11) // x
b2 = candidate ** 2
if (b2 - 11) % a == 0:
print(a, candidate)
lstb.append(candidate)
b = candidate
foundB = True
break
print(len(lstb) - 1)
count = 0
for tmp in lstb:
if tmp > 1 and tmp < max_num:
count += 1
print(count)
Problem Loading...
Note Loading...
Set Loading...
This problem is an example of the Vieta Root Jumping technique. One may want to look at simpler Vieta Root Jumping problems first before jumping (pun intended) into this one.
First, note that for coprime pairs a , b the conditions a ∣ ( b 2 − 1 1 ) , and b ∣ ( a 2 − 1 1 ) are equivalent to a single condition: a b ∣ ( a 2 + b 2 − 1 1 ) .
Suppose a b a 2 + b 2 − 1 1 = n . This can be rewritten as b 2 − n a b + ( a 2 − 1 1 ) = 0 So b is one of the roots of the quadratic equation x 2 − ( n a ) x + ( a 2 − 1 1 ) = 0 . The other root, which is also integer, can be written as c = n a − b or b a 2 − 1 1 .
If a 2 − 1 1 > 0 , then a 2 − 1 1 , a 2 < a b , so 0 < c < a . Also, g c d ( c , a ) = g c d ( n a − b , a ) = g c d ( a , b ) = 1 . Therefore, the pair ( c , a ) also satisfies the same conditions as ( a , b ) , for the same n .
We apply the above argument repeatedly to any solution ( a , b ) until we get a pair ( a 0 , b 0 ) such that a 0 2 − 1 1 < 0 . Note that we can recover the original solution by "jumping back": in the argument above ( a , b ) = ( a , n a − c ) .
If a 0 2 − 1 1 < 0 , we get, since a 0 > 0 , three possibilities: a 0 = 1 , 2 , 3 .
Case 1. a 0 = 3 . Then b 0 2 − 3 n b 0 − 2 = 0 , so b 0 ( b 0 − 3 n ) = 2 . This implies b 0 ≤ 2 , which contradicts a 0 < b 0 . So this case is impossible.
Case 2. a 0 = 2 . Then, similar to the above, we get b 0 ( b 0 − 2 n ) = 7 . Since b 0 > a 0 , this implies that b 0 = 7 . So n = 3 . By jumping back this pair ( a 0 , b 0 ) leads to solutions ( u i , u i + 1 ) , where the sequence { u i } is given by condition u 0 = 2 , u 1 = 7 ; u i + 1 = 3 u n − u n − 1 : 2 , 7 , 1 9 , 5 0 , 1 3 1 , 3 4 3 , . . .
Case 3. a 0 = 1 . Then we get b 0 ( b 0 − n ) = 1 0 . This has three solutions: b 2 , n = − 3 , b 0 = 5 , n = 3 , and b = 1 0 , n = 9 . Note that the first pair, ( a 0 , b 0 ) = ( 1 , 2 ) , cannot be jumped into, because b 2 − 1 1 is already negative, so the process would have stopped one step earlier. The other two pairs do lead to infinite series of solutions. The pair ( 1 , 5 ) gives a sequence ( v i , v i + 1 ) , where v 0 = 1 , v 1 = 5 ; v i + 1 = 3 v i − v i − 1 . The pair ( 1 , 1 0 ) gives a sequence ( w i , w i + 1 ) , where w 0 = 1 , w 1 = 1 0 ; w i + 1 = 9 w i − w i − 1 .
In order to count the number of solutions with b < 1 0 1 0 0 we need to find out how fast these sequences grow. Note that they are similar to the Fibonacci sequences, and grow exponentially. The general theory of linear recursive sequences allows us to find the formulas for them.
Lemma. Suppose s = 2 3 + 5 and t = 2 9 + 7 7 . Then for all i we have u i = 5 5 + 4 s i + 5 5 − 4 s − i ,
v i = 2 5 5 + 7 s i + 2 5 5 − 7 s − i ,
w i = 2 7 7 + 1 1 t i + 2 1 1 7 − 1 1 t − i .
Proof. Note that s and s − 1 are the two roots of the equation x 2 = 3 x − 1 , while t and t − 1 are the two roots of x 2 = 9 x − 1 . The general theory implies that u i = α s i + β s − i for some α and β . Using i = 0 and i = 1 , we get α = 5 5 + 4 and β = 5 5 − 4 . The resulting formula is easy to prove by induction. The other two formulas are obtained in the same way.
Now note that s − 1 and t − 1 are less than 1 , so their powers decay exponentially. So for large i u i is approximately equal to 5 5 + 4 s i . So using logarithms, one can easily check that the largest u i < 1 0 1 0 0 is u 2 3 8 . Likewise, the largest v i < 1 0 1 0 0 is v 2 3 8 , and the largest w i < 1 0 1 0 0 is w 1 0 5 .
So, we have a pair ( 1 , 2 ) , 2 3 8 pairs of type u , 2 3 9 pairs of type v , and 1 0 5 pairs of type w . This gives 1 + 2 3 8 + 2 3 8 + 1 0 5 = 5 8 2 pairs.