Mathematica s PrimeQ returns True

PadovanNumber =
DifferenceRoot[
Function[{[FormalY], [FormalN]}, {-[FormalY][[FormalN]] -
[FormalY][1 + [FormalN]] + [FormalY][3 + [FormalN]] ==
0, [FormalY][0] == 1, [FormalY][1] == 1, [FormalY][2] == 1}]];

PrimeQ[PadovanNumber[536485]]
True

To be completed...