0
$\begingroup$

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$$

$\endgroup$
4
  • $\begingroup$ try (4,3) ------------ $\endgroup$
    – user525678
    Jan 28, 2018 at 18:05
  • $\begingroup$ $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. $\endgroup$
    – fleablood
    Jan 28, 2018 at 18:42
  • $\begingroup$ $(y-1)! \equiv 0 \mod y$ if $y$ is not prime. So $k*(y-1)! \equiv (y-1)!\mod y$ most certainly does NOT mean $k \equiv 1 \mod y$. Not $53^7 \equiv 5 \mod 8$. $\endgroup$
    – fleablood
    Jan 28, 2018 at 18:50
  • $\begingroup$ If $y = m*n$ where $1 < m,n < y$ then $(y-1)! = 1*.....*m*.....*n*.....*(y-1)$ and so $mn|(y-1)!$ so $(y-1)! \equiv 0 \mod y$. So $x^k*(y-1)! \equiv (y-1)! \mod y$ for any composite $y$ no matter what $x$ and $k$ are. This in no way implies $x^k \equiv 1$. $\endgroup$
    – fleablood
    Jan 28, 2018 at 18:54

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ One doubt, How did you write 53^7 as 5^7. $\endgroup$ Jan 29, 2018 at 3:20
  • $\begingroup$ 53=48+5. So $53^7\5^7\mod 8$. $\endgroup$
    – fleablood
    Jan 29, 2018 at 4:12
0
$\begingroup$

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)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .