Well, if has order modulo , i.e. is the least positive integer such that , then for any exponent such that , we must have .
Hence if , this means that the order of must divide ...
Extra hint : to show that , you can use the "second supplement" to the quadratic reciprocity law, which states that for any odd prime .