We determine the exact order of the companion matrix associated with the Padovan recurrence modulo prime powers. In particular, we prove that the matrix has exact order 39 in GL₃(ℤ/9ℤ). The argument combines irreducibility over F₃, identification with the finite field F₂₇, and a first-order lifting mechanism. We further establish a general theorem describing how the order grows under lifting from modulo p to pᵏ. Keywords: Padovan sequence, finite fields, matrix order, lifting modulo prime powers