Prove that $n|2^{(n-1)!}-1$ for any $n = 2k + 1$ given $k$ is a natural number

Question

What i have done so for:

$2^{(n-1)!} \equiv 1 (mod\hspace 1 mmn)$
Thought about wilson`s theorem but $n$ is not a prime.
Tried to break the factorial and reduce the congruence to $2^{(n-2)!}$ but not sure this is the right way to do.

Any advice would be highly appreciated.

If $n=2k+1$ then $n$ and $2$ are relatively prime. So $2^{\phi(n)}\equiv 1 \pmod n$. — fleablood, Feb 09 '22 at 05:48
@Mabadai FYI, by using Approach0, I was able to find the very similar Let n be an odd positive number. Prove that n | $(2^{n!}-1)$.. — John Omielan, Feb 09 '22 at 05:55
@fleablood Are $n$ and $2$ relatively prime because of Euclid`s Division Theorem? — Mabadai, Feb 09 '22 at 06:07
Thanks @JohnOmielan i found the linked question more useful link — Mabadai, Feb 09 '22 at 06:08

MH.Lee · Accepted Answer · 2022-02-09T05:53:42.370

7

If $n$ is odd, then surely $(2,n)=1$. So you can use Fermat's Little Theorem(Euler's Generalization).

And also, $\phi(n)<n$ holds, so $\phi(n)\mid(n-1)!$.

Let $(n-1)!=m\phi(n)$, then $2^{(n-1)!}=2^{m\phi(n)}=(2^{\phi(n)})^m\equiv1^m=1\pmod n$.

edited Feb 09 '22 at 05:53

answered Feb 09 '22 at 05:51

MH.Lee

5,568

3

Nitpick.... FLT is when $n$ is prime. Euler's Theorem is for relatively prime moduli. – fleablood Feb 09 '22 at 05:53
Thanks @fleablood. I learned this theorem as Euler's generalization of FLT, so I confused. – MH.Lee Feb 09 '22 at 05:54
Oh... I never thought of it like that. – fleablood Feb 09 '22 at 05:58

score 3 · Answer 2 · answered Feb 09 '22 at 05:52

HINT: $\varphi(n)$, where $\varphi(n)=\left|\left(\mathbb{Z}/n \mathbb{Z}\right)^×\right|$, divides $(n-1)!$, and $2\in \left(\mathbb{Z}/n\mathbb{Z}\right)^×$, because $n$ is odd. Finish using Euler's Thm. [Mistakenly called it Fermat, thanks @fleablood in the comments for the correction]

Prove that $n|2^{(n-1)!}-1$ for any $n = 2k + 1$ given $k$ is a natural number

2 Answers2