It turns out that the largest power i of 2 such that 2i < n for any odd integer n is involved in many other interesting theorems and I'm very much tempted to give it a special definition but I shall refrain from doing so until I prove more of the theorems associated with it.
Theorem: If n is an odd integer and i is the largest power of 2 such that 2i < n then
2i+1 (mod n) = 2i - r for some integer r such that r = n - 2iProof: If n is an odd integer then n can be represented as n = 2i + r for some integer r such that 2i-1 < r < 2i
Since n = 2i + r then 2i = (n - r) and also since 2i+1 (mod n) = 2*2i (mod n) then 2i+1 (mod n) = 2*(n - r) (mod n)
Clearly, since 2i-1 < r < 2i then 2*(n - r) < 2*n so
2i+1 (mod n) = 2*(n - r) (mod n)= 2*(n - r) - n = ( 2*2i ) - n = ( 2*2i )- (2i + r) = 2i+2i - 2i - r = 2i - r .'.
Example: Let n = 35, then the largest power i of 2 mod 35 such that 2i < 35 is i = 5 since 25 = 32 and 32 is congruent to 32 (mod 35) so no modular arithmetic is needed to compute this power.
However, for all i > 6 then 2i > 35 and so modular arithmetic will be needed to compute such powers unless of course I use the method I described here and its improved version here, which generate all powers of 2 mod n without using modular arithmetic, multiplication, or exponentiation.
If I'm only interested in the value of 26 mod 35 then by the theorem above 2i+1 mod n = 26 mod 35 = 32 - (35 - 32) = 29
This is obviously insignificant but it is still interesting because computing 2i+1 will not exceed n using this formula.