# Residue of powers of a prime modulus another prime.

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.

• 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? – lulu Jan 12 at 21:28
• 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. – aaac991 Jan 12 at 21:34
• 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)$? – lulu Jan 12 at 21:44
• Should note: Adding $p$ to the numerator doesn't change the expression $\pmod p$. – lulu Jan 12 at 21:45
• Thanks for your comments, I have edited the post again and I believe it is now more understandable. – aaac991 Jan 12 at 22:28