Question

Show that 66013 is not a prime by using the contrapositive of Fermat's Little Theorem:
If x^(p-1) not = 1 mod p, then p is not a prime.
Now I can do this for a small number like 39 using x = 2 but I'm unsure how to proceed with such a large number.

Answer 1

Not sure anyone knows of Fermat's Theorem on here...

It sounds familiar but I'm not about to tutor in calculus when I barely passed with an average of B lol

Answer 2

this is an old question but still hasn't been answered yet @hero @angle would you mind taking a shot at this? the math is a little above my skill level i think

Answer 3

ok thanks

Answer 4

they already told you to start the proof via contrapositive, so you know where to start and it should be straightforward:
x^(p-1) not = 1 (mod p)
so for p=66013 , you simply wish to pick an example number that yields a remainder that is not equal to one.
If you're familiar with modular exponentiation this should be a trivial task, say choosing x=10 to yield expression
10^(66012) ?= 1 (mod 66013)
Do yourself a favor and google modular exponentiation.

Answer 5

also @Vocaloid i'm almost offended you didn't tag me in a basic number theory question seeing as I took introductory group theory :(

Answer 6

@celticcat

Answer 7

OK Ill do that. thank you

Answer 8

let me know if you have any questions. The choice of x should not matter since none of them should work, but I've chosen x=10 in hopes it will be easier to work with