Currently, main Cloud service venders employ the template-based virtual machine (VM) deployment method in their Cloud data center to reduce the startup latency of user VMs. However, because of the large size of VM templates, usually, limited number of them can be stored by a Cloud data center. In the face of the large scale deployment requirements of user VMs with various application purposes in the Cloud data center, the limited number of VM templates can not support the quickly deploying of all user VMs to be deployed in the Cloud data center. Hence, the optimal VM template provisioning and management is a challenging work in a Cloud date center. In this paper, we propose a mechanism, the Representative Virtual Machine Templates (RVMTs), by which the rapid deployments for a large scale of user VMs with different application purposes in a Cloud data center can be achieved with limited number of representative virtual machine templates stored, to solve the problem of the optimized provisioning and management of VM templates in a Cloud data center. We formulate the finding of RVMTs as an optimization problem with given constraints and introduce the K-medoids Clustering-based RVMTs finding algorithm to solve it. We also theoretically prove that this algorithm can achieve the optimal result. On the implementation side, we design a RVMTs management system, called RVMTMS, to achieve the RVMTs mechanism.