Number Theory - Elliptic Curves: Number Theory and Cryptography - page 469

THEOREM A.1 (Chinese Remainder Theorem)
Let n 1 ,n 2 ,...,n r be positive integers such that gcd( n i ,n j )=1 when i = j.

Let a 1 ,a 2 ,...,a r be integers. Then there exists an x such that

x ≡ a i (mod n i ) for all i.

The integer x is uniquely determined mod n 1 n 2 ···n r .

For example, let n 1 =4 ,n 2 =3 ,n 3 =5andlet a 1 =1 ,a 2 =2 ,a 3 =3.
Then x = 53 is a solution to the simultaneous congruences

x ≡ 1(mod , x ≡ 2(mod , x ≡ 3(mod ,

and any solution x satisfies x 53 (mod 60).

Another way to state the Chinese Remainder Theorem is to say that if
gcd( n i ,n j )=1for i

≡

= j ,then

Z n 1 n 2 ···n r Z n 1 ⊕···⊕ Z n r

(see Appendix B for the definition of ⊕ ). This is an isomorphism of additive
groups. It is also an isomorphism of rings.

p-adic numbers

Let p be a prime number and let x be a nonzero rational number. Write
x = p r a

b ,

where a, b are integers such that p ab .Then r is called the p -adic valuation

of x and is denoted by

r = v p ( x ) .
Define v p (0) = ∞ .(The p -adic valuation is discussed in more detail in Sections
5.4 and 8.1.) The p -adic absolute value of x is defined to be

| p = p −r .

| x

Define | p =0.

For example,

| 0

2 5

41 3

12
35

= 1

11
250

1
2 −

1
81 . 4 ,

= 125 , =

The last example says that 1 / 2 and 41 are close 3-adically. Note that two
integers are close p -adically if and only if they are congruent mod a large
power of p .