Finding factor with primes

Question

If $p$ is a prime other then $2$, express the general prime factor of $2^p-1$ in terms of p and some other integer.

Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. If this is homework, please add the homework tag; people will still help, so don't worry. Also, many find the use of imperative ("Prove", "Solve", etc.) to be rude when asking for help; please consider rewriting your post.

lab bhattacharjee · Accepted Answer · 2012-11-04 11:09:26Z

up vote 2 down vote accepted

Let prime $q\mid (2^p-1)\implies ord_q2\mid p$

If $ord_q2=1,2^1\equiv 1\pmod q\implies q\mid (2-1)$ which is impossible.

SO, $ord_q2=p$ and $ord_q2\mid\phi(q)\implies p\mid\phi(q)\implies p\mid(q-1)$

For prime $q>2,q-1$ is even as $q$ must be odd.

So, $2\mid (q-1)\implies lcm(2,p)\mid (q-1)$

But $lcm(2,p)=2p$ as $p$ is odd.

So, $2pk=q-1\implies q=2pk+1$ for some natural number $k$

edited Nov 4 '12 at 11:09

answered Nov 4 '12 at 10:59

lab bhattacharjee
27.9k12346

	Hey, I've just started studying number theory. When you refer to $\phi(q)$ do you mean the Euler $\phi$-function? which counts the number of integers smaller then q which have a gcd of 1 with q? Also what does $ord_q2\|p$ actually represent? – user48133 Nov 4 '12 at 11:58
	@user48133, yes its Euler $\phi$ function. $ord_qa$ multiplicative/modulo order(mathworld.wolfram.com/MultiplicativeOrder.html) – lab bhattacharjee Nov 4 '12 at 12:14

1 Answer