# Thread: Little Fermat's Theorem Question

1. ## Little Fermat's Theorem Question

Sorry I'm very new to this stuff.

Could someone explain to me how to do the following question please?:

"Let p = 11, and a = 3. Explain why you can apply the Little Fermat's Theorem: a^(p-1) ≡ 1 (mod p). Verify this theorem directly by using the given numbers p and a."

Any help would be greatly appreciated!

2. Originally Posted by s3a
Sorry I'm very new to this stuff.

Could someone explain to me how to do the following question please?:

"Let p = 11, and a = 3. Explain why you can apply the Little Fermat's Theorem: a^(p-1) ≡ 1 (mod p). Verify this theorem directly by using the given numbers p and a."

Any help would be greatly appreciated!
There is one important condition that must be met in order to apply Fermat's little theorem. So what observation can be made between those two numbers?

Spoiler:
What is $\gcd(3,11)$ equal to?

3. They're both prime and therefore relatively prime?

4. Originally Posted by s3a
They're both prime and therefore relatively prime?
Correct. Now, in general, Fermat's theorem $a^p\equiv a\pmod{p}$ works for any integer $a$ and prime $p$. However, in order to define $a^{-1}$, one requires that $\gcd(a,p)=1$. Then $a^p\equiv a\pmod{p}\implies a^{p-1}\equiv 1\pmod{p}$, which is Fermat's little theorem.

Now, all that's left to do is verify that $3^{10}\equiv 1\pmod{11}$. Can you proceed from here?

5. Sorry for the dumb question but, to answer this particular question, do I need to say all that if this were a test for example or is it enough to say that they're both prime and therefore relatively prime and then just plug in the values and demonstrate (not prove) that it works?

6. Originally Posted by s3a
Sorry for the dumb question but, to answer this particular question, do I need to say all that if this were a test for example or is it enough to say that they're both prime and therefore relatively prime and then just plug in the values and demonstrate (not prove) that it works?
I think you have to compute $3^{10}\pmod{11}$ and end up with $1\pmod{11}$. So yes, you need to do the computation to show that the result of the theorem is true. Do you know how to do the computation?

7. Originally Posted by s3a
Sorry for the dumb question but, to answer this particular question, do I need to say all that if this were a test for example or is it enough to say that they're both prime and therefore relatively prime and then just plug in the values and demonstrate (not prove) that it works?

What is important is that p is prime and a is coprime with it. Of course, if a is also prime then it's easier

to check coprimality, but the question has the very same output for a = 6, 8 or 0,

say and none of these is prime and it's also very easy to show coprimality)

Tonio

Pd. I'm gonna do copyright of that word, coprimality, which I believe exists only in

my imagination but not in the english language...