Fully homomorphic encryption (FHE) is a useful cryptographic primitive. It makes a third-party manipulate data in the ciphertext space and therefore is a key technology for privacy-preserving outsourcing services. Theoretically, FHE can evaluate any circuits. However, the implementation is not trivial. The reason it lacks lots of basic operations like conditional check and branch control. In this paper, we focus on extended Euclidean algorithm operation over FHE. We introduce the problems we encounter and show how we solve these issues. We implement our design and evaluate its performance on a real computer. Finally, we propose some research directions for our future work.