this is just condition here is problem

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?

  • $\begingroup$ 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. $\endgroup$ – fgrieu Dec 11 '16 at 20:34
  • $\begingroup$ I want to know how to prove that last part.. $\endgroup$ – 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.$

| improve this answer | |
  • $\begingroup$ Oh I see, sorry read it too quickly. $\endgroup$ – CurveEnthusiast Jan 12 '17 at 11:55

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.