Question

Let us go over these 3 theorems today

Fermat's Little theorem
Euler's Phi function
Euler's totient theorem

Answer 1

To work out\[\large 2^{6} \pmod{7}\]

consider the product
\[(1\cdot 2) (2\cdot 2)(3\cdot 2)(4\cdot 2)(5\cdot 2)(6\cdot 2) = 6! 2^6 \]

Answer 2

I think the totient and phi function are just two names for the same thing. As far as I know, phi(n) is the total number of numbers less than n such that GCD(n, k)=1. So phi(6)=2 since GCD(1,6)=1 and GCD(1,5)=1 and there are no other numbers less than 6 that have a GCD with 6 that is 1, since obviously GCD(2,6)=2 and GCD(4,6)=2 for example.

Answer 3

Notice that the left hand side reduces to \(6!\) if you take mod 7

thats the fermat's little theorem :
\[(p-1)! \equiv (p-1)!a^{p-1} \pmod{p}\]
whenever \(p\nmid a\)

Answer 4

(The idea is same as the one used in counting number of elements in a set whose remainders are greater than p/2.)

simply cancel (p-1)! both sides as p does not divide (p-1)!

Answer 5

oh ok i see the totient thing euler found a function that outputs the number of these sets ?

Answer 6

so it goes back to that old stuff we did