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

In summary, the homework statement proves or disproves that: if x is an odd number greater than 1, then residue classes of 2^x mod N are equal to the number of odd residue classes of 2^x \bmod N.
  • #1
Floating Info
8
0

Homework Statement



Prove or disprove that:

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

Is equal to the number of odd residue classes of [itex]2^x \bmod N[/itex] 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 [itex]2^x \bmod N[/itex] 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:

[itex]2^0[/itex] = 1
[itex]2^1[/itex] = 2
[itex]2^2[/itex] = 4
[itex]2^3[/itex] = 8
[itex]2^4[/itex] = 16
[itex]2^5[/itex] = 32
[itex]2^6[/itex] = 29
[itex]2^7[/itex] = 23
[itex]2^8[/itex] = 11
[itex]2^9[/itex] = 22
[itex]2^{10}[/itex] = 9
[itex]2^{11}[/itex] = 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.
 
Last edited:
Physics news on Phys.org
  • #2
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:

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

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
 
  • #3
rcgldr said:
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.
 
Last edited:
  • #4
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.
 
  • #5
Joffan said:
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.
 
  • #6
Floating Info said:
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.
 

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

1. What is the summation of powers of two mod n equivalence to the number of odd residues?

The summation of powers of two mod n equivalence to the number of odd residues is a mathematical concept that states that the sum of all powers of two (2^0, 2^1, 2^2, etc.) modulo n is equal to the number of odd residues in the modulo n system.

2. How is this concept useful in mathematics?

This concept is useful in various mathematical fields such as number theory, cryptography, and computer science. It helps in solving problems related to modular arithmetic and can be used in algorithms and proofs.

3. Can you provide an example of this concept in action?

Sure, let's take the number 5 and the modulo system modulo 7. The powers of two in this system would be 1, 2, 4, 1, 2, 4, etc. The sum of these powers modulo 7 would be 1+2+4=7, which is congruent to 0 modulo 7. This means that there are no odd residues in this system, as expected.

4. Are there any limitations to this concept?

Yes, this concept is only applicable when the modulo n system is relatively prime to 2. This means that n and 2 have no common factors other than 1. If this condition is not met, then the summation of powers of two may not be equal to the number of odd residues.

5. Is there any real-world application of this concept?

Yes, this concept is used in various applications such as error-correcting codes, data compression, and pseudorandom number generation. It also has applications in the fields of engineering, physics, and economics.

Similar threads

Back
Top