Summation of Powers of Two Mod N equivalence to # of odd residues

[Floating Info]

Homework Statement

Prove or disprove that:

\frac{{\sum_{i=0}^{ord_N (2) - 1}} (2^i \bmod N)}{N}

Is equal to the number of odd residue classes of 2^x \bmod N for all odd numbers N greater than 1.

Homework Equations

Residue Classes are the residues that are generated by a function mod N.

The Attempt at a Solution

I've tried to split up the residue classes of 2^x \bmod N into different sets, each starting with an odd and including the evens directly after it. I've then added up the elements of each set and subtracted the sum of each set by the modulus. If this is true, the sum of all of these results from the sets should always equal 0. Here is an example for 35:

2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
2^5 = 32
2^6 = 29
2^7 = 23
2^8 = 11
2^9 = 22
2^{10} = 9
2^{11} = 18

{1 + 2 + 4 + 8 + 16 + 32 - 35}
{29 - 35}
{23 - 35}
{11 + 22 - 35}
{9 + 18 - 35}

28 - 6 - 12 - 2 - 8 = 0

However, I have found no significant pattern in these values across different moduli that would suggest that it should always equal 0.

I've also used Mathematica to check all cases up to 9999.

 

[rcgldr]

I've only done some work with finite fields, mostly for error correction code, but since there haven't been any responses yet, I'll try.

For the first step, I assume you can change this to:

{\sum_{i=0}^{ord_N (2) - 1}} (2^i \bmod N) = N ({odd\_residue\_classes})

Then is there some way to eliminate the modulo? For example if y is prime and if (x · a) mod y = 1, (a being the inverse of x mod y) then there is a negative integer b where

x · a + y · b = 1

 

[Floating Info]

Then is there some way to eliminate the modulo? For example if y is prime and if (x · a) mod y = 1, (a being the inverse of x mod y) then there is a negative integer b where

x · a + y · b = 1

Two questions:

1. What exactly do you mean by eliminate the modulo?

2. Instead of if y being prime, do you mean if x and y are coprime? The equation would still apply, and, assuming that the b can be used for something, it would prove a vastly more general result.

 

[Joffan]

Tricky. Not really pre-calculus, I'd say.

It does feel true, since we know the total of the residues ($\equiv (2^{ord_N(2)}-1) \pmod N$) must be divisible by N and your partial sums $S_i$ are bounded by $N/2 < S_i < 2(N-1)$. But it's hard to see a way through.

Using your example suggests a pattern

1+2+4+8+16+32-35=28

28+29-35 = 22

22+23-35 = 10

10+11+22-35 = 8

8+9+18-35 = 0

Each time we roll the clock, our partial sum is one less than the next number. And we finish when the clock rolls to zero (because the next number would be 1 again). And there's only one odd number in each set.

Hope this helps.

 

[Floating Info]

Tricky. Not really pre-calculus, I'd say.

It does feel true, since we know the total of the residues ($\equiv (2^{ord_N(2)}-1) \pmod N$) must be divisible by N and your partial sums $S_i$ are bounded by $N/2 < S_i < 2(N-1)$. But it's hard to see a way through.

Using your example suggests a pattern

1+2+4+8+16+32-35=28

28+29-35 = 22

22+23-35 = 10

10+11+22-35 = 8

8+9+18-35 = 0

Each time we roll the clock, our partial sum is one less than the next number. And we finish when the clock rolls to zero (because the next number would be 1 again). And there's only one odd number in each set.

Hope this helps.

It does help.

I put this in Pre-Calc since I didn't know the difficulty of it, just the difficulty of stating it. I suspected the proof was simple.

 

[rcgldr]

1. What exactly do you mean by eliminate the modulo?

2. Instead of if y being prime, do you mean if x and y are coprime? The equation would still apply, and, assuming that the b can be used for something, it would prove a vastly more general result.

1. If there was some way to add variables and eliminate the modulo, such as the example I gave.

2. If y is prime, then x and y are coprime for any integer x. In the finite field math I use (Reed Solomon based error corrrection code), it's always done modulo some prime number, and I'm only interested finding the inverse for x modulo y, not a more general solution that also finds the inverse of y modulo x.

I only replied because I didn't see any other replies and was thinking that any suggestion would be better than none.