Fermat's Little Theorem is applicable for any 2 Co-primes?

Question

I am confused with the results that I saw. I don't see where I am thinking wrong.

According to Fermat's Little Theorem. $$a^{p-1} \equiv 1\bmod p$$ where G.C.D(a,p) = 1 and p is prime number.

but this seems to hold for any to co-primes like

$$y^{x-1} \equiv 1\bmod x$$ where G.C.D(x,y) = 1 and x is any number.
Some Code Snippet of Python.

def func(x,y):
    for i in range(1,x):
        print("{0} % {1} = {2}".format(y * i ,x, (y * i)%x))

Ex: func(6,13)
13 % 6 = 1
26 % 6 = 2
39 % 6 = 3
52 % 6 = 4
65 % 6 = 5

$$13 * 26 * 39 * 52 * 65 = 13^{5} * 5!$$ $$13^{5} * 5! \equiv 5! \bmod 6$$ $$13^{6-1} \equiv 1 \bmod 6$$

Ex: func(8,53)
53 % 8 = 5
106 % 8 = 2
159 % 8 = 7
212 % 8 = 4
265 % 8 = 1
265 % 8 = 6
371 % 8 = 3
$$53 * 106 * 159 * 212 * 265 * 265 * 371 = 53^{7} * 7!$$ $$53^{7} * 7! \equiv 7! \bmod 8$$ $$53^{8-1} \equiv 1 \bmod 8$$

But in calculator i get $$53^{7} \bmod 8 = 5$$

I tried with several co-primes and ended in same conclusion.

Is it also true or I am wrong?

Edit: @fleablood, Thanks for the comment.

I came to know my mistake. I need to take care of modular division.

Since I cannot divide both side by a common factor without the GCD(common_factor,N) = 1 in mod N world.

$$x^{y−1}∗(y−1)!≡(y−1)!\bmod y \nRightarrow x^{y−1}≡1 \bmod y$$

Answer 1

If I understand your question correctly, the answer is given by group theory. The fact that

$$ a^{p-1} \equiv 1 \mod p $$

follows from the fact that the group of units of $\mathbb{Z}/p\mathbb{Z}$ has order $\varphi(p)=p-1$, where $\varphi$ is the Euler totient function. Therefore, any unit in $\mathbb{Z}/p\mathbb{Z}$ (i.e. any integer $a$ coprime with $p$) to the power $p-1$ is $1$, because $p-1$ is the order of the group.

Same applies word by word to $\mathbb{Z}/N\mathbb{Z}$ and its group of units. This group is not cyclic anymore if $N$ is not a prime number (hint: use the Chinese Reminder Theorem to compute this group). The order of this group of units is given by $\varphi(N)$, which you can easily compute.

In general, $\varphi(N)\neq N-1$, and this is the reason why your claim is not going to be true in general.

Counterexample: consider $N=15=3\cdot 5$. By the CRT we have

$$(\mathbb{Z}/15\mathbb{Z})^{\times } \cong (\mathbb{Z}/3\mathbb{Z})^{\times } \times (\mathbb{Z}/5\mathbb{Z})^{\times }$$

Now $N-1=15-1=14$. So you want to know if every element in the previous group to the power $14$ is $1$. Without any computation, you can already see that the answer is no: consider $(1,a)$ for $a\neq 1 $ in $(\mathbb{Z}/5\mathbb{Z})^{\times }$. Then $a$ has order $\varphi(5)=4$. In particular, $a^{14}\neq 1$ in $(\mathbb{Z}/5\mathbb{Z})^{\times }$, so $$(1,a)^{14} \neq (1,1)$$

Answer 2

No.

It's not true. Try $3^{15} \equiv 11 \mod 16$

The correct formula is

$y^{\phi(x)}\equiv 1 \mod y$.

Where $\phi$ is the Euler totient function. If $p$ is prime then $\phi(p) = p-1$ but other wise $\phi(x) \ne x-1$.

Your mistake:

$x^{y-1} * (y-1)! \equiv (y-1)!\mod y \not \implies x^{y-1} \equiv 1 \mod y$. This is only true if $\gcd((y-1)!, y) = 1$ which is never the case if $y$ is not prime.

In fact if $y$ is not prime then $(y-1)! \equiv 0 \mod y$ for pretty obvious reasons.

So so $53^7*7! \equiv 0 \equiv 7! \mod 8$

That certainly does not meant $53^7 \equiv 1 \mod 8$

And indeed $53^7 \equiv 5^7$ and as $\phi (8) = 4$ then $5^7 \equiv 5^3 \equiv 5 \mod 8$.