Euclidean algorithm Āryabhaṭa Euclid
Āryabhaṭa (476–550 AD) showed that pairs of simultaneous congruences 



n
≡

a

1




mod

m



1




{\displaystyle n\equiv a_{1}{\bmod {m}}_{1}}

, 



n
≡

a

2




mod

m



2




{\displaystyle n\equiv a_{2}{\bmod {m}}_{2}}

 could be solved by a method he called kuṭṭaka, or pulveriser; this is a procedure close to (a generalisation of) the Euclidean algorithm, which was probably discovered independently in India. Āryabhaṭa seems to have had in mind applications to astronomical calculations.
