Elliptic Curves over Q - Elliptic Curves: Number Theory and Cryptography - page 219

be points on E ,where y i ∈ Q and a i ,b i are integers with gcd( a i ,b i ) = 1. Let

g 1 =2( a 1 b 2 + a 2 b 1 )( Ab 1 b 2 + a 1 a 2 )+4 Bb 1 b 2
g 2 =( a 1 a 2 − Ab 1 b 2 ) 2 − 4 B ( a 1 b 2 + a 2 b 1 ) b 1 b 2

a 2 b 1 ) 2 . g 3 =( a 1 b 2 −

Then a short calculation shows that
a 3
b 3

+ a 4
b 4

= g 1

a 3 a 4
b 3 b 4

= g 2

g 3 , g 3 .

LEMMA 8.20
Let c 1 ,c 2 ,d 1 ,d 2 ∈

Z .Then

Max( |c 1 |, |d 1 | ) · Max( |c 2 |, |d 2 | ) ≤ 2Max( |c 1 c 2 |, |c 1 d 2 + c 2 d 1 |, |d 1 d 2 | ) .

PROOF (other-

wise, switch c 1 ,d 1 ). Let L denote the left side of the inequality of the lemma
and let R denote the right side. There are three cases to consider.

Without loss of generality, we may assume that | c 1 |≤| d 1 |

1. If | c 2 |≤| d 2 | ,then L = | d 1 d 2 | and 2 | d 1 d 2 |≤ R ,so L ≤ R .

2. If | c 2 |≥| d 2 |≥ (1 / 2) | c 2 | ,then L = | d 1 c 2 | and

R ≥ 2 |d 1 d 2 |≥|d 1 c 2 |≥L.

3. If |d 2 |≤ (1 / 2) |c 2 | ,then L = |d 1 c 2 | and

R ≥ c 1 d 2 + c 2 d 1 |

≥ 2( |c 2 d 1 |−|c 1 d 2 | )
≥ 2( |c 2 d 1 |−|d 1 | (1 / 2) |c 2 | )
= |c 2 d 1 | = L.

2 |

This completes the proof of the lemma.

LEMMA 8.21
Let c 1 ,c 2 ,d 1 ,d 2 ∈ Z with gcd( c i ,d i )=1 for i =1 , 2 .Then

gcd( c 1 c 2 ,c 1 d 2 + c 2 d 1 ,d 1 d 2 )=1 .

PROOF Let d =gcd( c 1 d 2 + c 2 d 1 ,d 1 d 2 ). Suppose p is a prime such that
p|c 1 and p|d .Then p d 1 since gcd( c 1 ,d 1 ) = 1. Since p|d 1 d 2 ,wehave p|d 2 .
Therefore, p c 2 . Therefore, p|c 1 d 2 and p c 2 d 1 ,so p c 1 d 2 + c 2 d 1 . Therefore
p d , contradiction. Similarly, there is no prime dividing both c 2 and d .It