1
$\begingroup$

Given different primes a and p we know by Fermat's little theorem that

$$a^{p-1} \equiv 1 \pmod{p}. $$

In the case of a = 2, a sequence for

$$ 2^{p-i} \equiv j_i \pmod{p}$$

can be written as

$$ f(i)= \begin{cases} j_i = \frac{j_{i-1}}{2} ,&\text{if } j_{i-1}\equiv 0 \pmod{2}\\ j_i = \frac{j_{i-1}+p}{2}, & \text{otherwise} \end{cases} $$

for $$1 < i \leqslant n$$ if $p \mid 2^{n}-1$, or $$1 < i \leqslant (p-1)$$ if it doesn't, and if $i = 1, j_i = 1$ because of Fermat's.

Taking p = 11 as an example, $j_1$ is going to be 1, and since 1 isn't even, $j_2 = 6$ with $2^{9} \equiv 6 \pmod{11}$, $j_3 = 3$, $j_4 = 7$ and so on up until $j_{10} = 2$ for which $2^{1} \equiv 2 \pmod{11}$.

With a number like $p = 23$, since it divides $2^{11} -1$, it's only going to have 11 values of $j_i$.

Since $2^{(p-1)n - (i+1)} \equiv 2^{(p-i)} \pmod{p}$ and given the conditions above, any power of two is going to be congruent with at most $n$ or $p-1$ number of unique $j_i$ mod p.

Now my question is if there's any way to generalize this for whichever different primes a and p.

$\endgroup$
8
  • 3
    $\begingroup$ This is very hard to follow. What is $j_i$? Is it $2^{p-i}$? I guess not. Is it defined to be $2^{p-i-1}$? Why? $\endgroup$ – lulu Jan 12 at 21:28
  • $\begingroup$ I'm sorry, I had a hard time making it clear. $j_i$ is going to be the value to which $a^{p-i}$ is congruent to modulus p, and its going to be different depending on the i, in this case the definition is concerning a = 2 so yes the value would be in regards to $2^{p-i}$. I've edited the post for clarity I hope. $\endgroup$ – aaac991 Jan 12 at 21:34
  • $\begingroup$ Please include the definition of $j_i$ in your post. As it is, it doesn't make sense. If $j_i=2^{p-i}$ then your definition of $f(s)$ is inconsistent. Why not include an explicit example? Take $p=11$. What are the $j_i$ in that case? What is $f(s)$? $\endgroup$ – lulu Jan 12 at 21:44
  • $\begingroup$ Should note: Adding $p$ to the numerator doesn't change the expression $\pmod p$. $\endgroup$ – lulu Jan 12 at 21:45
  • $\begingroup$ Thanks for your comments, I have edited the post again and I believe it is now more understandable. $\endgroup$ – aaac991 Jan 12 at 22:28

Your Answer

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

Browse other questions tagged or ask your own question.