# What's the link from $2^u-1$ to the multiplicative order?

I am reading this paper, but I will write everyting I need for my question here. So, long story short, we have a proth-number $$n$$, i.e. $$n = h\cdot 2^k+1$$ for odd $$h<2^k$$. We are looking for integers $$D$$ such that the Jacobi symbol $$\left(\frac{D}{n}\right) \neq 1.$$ I could already prove that $$\left(\frac{D}{n}\right) = \left(\frac{n}{D}\right),$$ so we can reduce $$n \pmod D$$. Now I know that $$h\cdot 2^k+1 \equiv (h\pmod D)\cdot 2^{k\mod ord_p(2)}\pmod D,$$ where $$ord_p(2)$$ is the order of $$2$$ modulo $$D$$. So of course we are interested in finding a $$D$$ with a possibly low order, because if $$D$$ is a solution for a $$k$$, then it's a solution for every $$k\pmod{ord_p(2)}$$. What I do not understand is this: In (4.1) of the paper, they say:

But I do not get the link. Why is it useful to factorize $$2^u-1$$?

• Please, use descriptive titles. "Problems understanding a paper" says nothing about the subject of the question. Mar 8 at 14:23

Any prime $$D$$ that divides $$2^u-1$$ satisfies $$2^u-1\equiv 0\pmod D$$, which means that $$2^u\equiv 1\pmod D$$, i.e. $$\mathrm{ord}_p(2)\mid u$$.
• More precisely, it is a way to find all primes for which $2$ has order $u$, because for all prime factors of $2^u-1$ the multiplicative order of 2 is $u$ (or smaller), and any prime $D$ for which $2^u\equiv1\pmod D$ must be a factor of $2^u-1$. Mar 8 at 16:03
• Do you maybe mean at most $u$? Because $2^{10}-1 = 3\cdot 11\cdot 31$ and the orders are $2,10,5$. Mar 8 at 16:14