# Finding greatest integer m satisfying modular relation

I solved (c). I want to know (a) and (b) For (a), what i have done is that p-1=t2^s(t is odd) = 2^s (mod 2^m) And for m=1,2,...s, both sides are 0. So, m is s or more than s. For m= s+1, s+2,... what will be the m?

• Hint: show that $p\equiv2^s+1\pmod{2^s}$, thus $m\ge s$. Then suppose $m>s$ and show than $s$ can't be up to it's definition. Conclude. – fgrieu Dec 11 '16 at 20:34
• I want to know how to prove that last part.. – nien Dec 12 '16 at 5:33

Question (a) does not seem right. Since, if $p=2^{n}+1$ then $s=n.$ But then every $m>s$ is valid. Indeed, $p-1 = 2^s\equiv 2^s \pmod{2^m}$ for every $m>s.$ Also, there are primes of the form $2^n+1$ e.g. $5,17,257,...$ In these cases, there is not an integer $m$ satisfying the properties you want. Assuming you don't have the previous case, in order to compute $m$ you have to find the order $\mod2$ of the number $t-1,$ where $t$ is the odd integer defined by the equality $p-1=t\cdot 2^{s},$ $t>1$. Equivalently, you have to find the largest integer $m$ such that $2^{m}|t-1.$