(^) is _not_ a method of Num, it is simply a function with a Num constraint. It will work on your new numbers as well as it would on any other that implements (*) correctly, you don't need to rewrite it.
By the way, your functions are dangerously partial, it would seem useful to put the prime into the type so that you can't add or multiply different Mod p. Of course this demands a bit more knowledge of Haskell type system than is likely in a beginner, but if you're motivated, I encourage you to look at numbers in type (see GHC.TypeLits maybe).
--