1
$\begingroup$

I found a proof about the infinite amount of primes. This proof uses basic concepts of group theory, which I'm not familiar with.

First they assume that the amount of prime numbers is finite and $p$ is the biggest prime. They want to show that every prime divisor $q$ of $2^p-1$ is bigger than $p$. In the next step it says that $2$ in the multiplicative group $\mathbb{Z}_q\backslash\lbrace 0\rbrace$ from $\mathbb{Z}_q$ has order $p$ ($p$ is the smallest integer with $2^p=1$), because of $p$ being prime.

Obviously $2^p\equiv 1 \mod q$ holds, but why isn't it possible that there is a smaller integer $r$ with $2^r\equiv 1 \mod q$?

I.e. after Euler's theorem is $a^{\varphi(n)}\equiv 1 \mod n$, when $a$ and $n$ are coprime. So it should be $2^{q-1}\equiv 1 \mod q$, because $q$ and $2$ are for $q\neq 2$ coprime and we assume $q$ to be prime. So why isn't it possible that $q-1$ is the order of $2$ in this group, because we don't know yet that $p<q$.

It contains math, I have never really used before, so it can be that I'm missing a really basic concept or an elementary idea.

$\endgroup$
5
$\begingroup$

Just one quick fact from group theory: let $G$ be a finite group and $g \in G$. If $g^n = 1$, then the order of $g$ divides $n$. (Proof: let $m$ be the order of $g$ and write $n = qm + r$ where $r < m$. Then $1 = g^n = g^{qm + r} = g^r$ and $r < m$, so $r = 0$ since $m$ is the smallest non-zero number with this property.)

So if $2^p$ is $1$ in $\mathbb{Z}/q\mathbb{Z}$, then the order of $2$ has to divide $p$; since $p$ is prime and the order of $2$ certainly isn't $1$, it must be $p$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.