We study the growth of matrix orders modulo prime powers, focusing on the transition from modulo p to modulo p^k. We establish a general lifting principle showing that, under a nontrivial first-order deformation, the order multiplies by a factor p^(k-1). As a concrete case, we analyze the companion matrix of the Padovan recurrence and prove that its order is 13 modulo 3 and exactly 39 modulo 9. The argument combines finite field methods over F3, identification with F27, and a structural analysis of the lifting mechanism.