|
|
|
Trivial solution: N = 0 works for all positive integers.
For powers of 2 (d = 2^k), d divides 2^k. It might not divide 2^k + k. However, we know that it divides all multiples of 2^k, including 2^(k+1), 2^(k+2), and so on, until we reach at most 2^(d). Then we know that d divides 2^d+d.
2^N % d = a.
Then 2^(N+1) % d = 2a % d Then 2^(N+2) % d = 4a % d And so on. If d is even, then eventually we'll find ka % d = 0, and multiples of that (N>k) can be used until the constant term +N comes around to a multiple of d.
time for classes... I'll give it another go later...
|
If d is even, then eventually we'll find ka % d = 0 d=6 start at N=2 2^2 % 6 = 4 = a 2^3 % 6 = 2 2^4 % 6 = 4 2^5 % 6 = 2 2^6 % 6 = 4 2^7 % 6 = 2 ... We'll never get to a 'k' for which ka%d=0
|
I'm tempted to say that any loop is fine, because we're adding increments of 1 to the total modulus with each next term.
The point was that if 2^N % d = 0, then we can increment N until the remaining +N is also divisible by d.
If we can't increase 2^N to be divisible by d, then obviously we have entered a loop, over which we can keep increasing the remaining +N until the total is divisible by d.
If any loop is okay, then this should work for odd numbers as well.
==== to summarize
For any d, take an arbitrary N.
Let a = 2^N % d Let b = N % d
If a + b = 0 or d, we are finished.
Now, we see if a * 2^k % d = 0 for any k. We need to increment k a maximum of d times before the modulus value begins looping or reaches 0.
In the case that it reaches 0, we only need to increment N a maximum of d more times before the value 2^N + N % d = 0.
In the case that it loops, we find the values of N where 2^(N+kb) % d = a. That is, the loop has a period of k numbers, and b is the number of total cycles. As long as k % d != 0, we can increment b until the constant added at the end matches up and the remainder becomes 0.
... I realize this still isn't proof to work for all numbers, just a lot of them...
|
Need a hint... will Fermat's Little Theorem come in handy here?
|
|
Hint: 1) if gcd(2,n) = 1 then 2^(phi(n)) = 1 (mod n) where phi(n) is the number of integers in {1,2,3,4,...n} that are relatively prime to n
2) Chinese remainder theorem
These are some of the standard tools for solving IMO-type problems.
Good luck!
|
I kinda wanna take a crack at this problem, but it also kinda feels like I'm doing discrete math homework all over again.
I'll probably give it a bit of a shot and give up because I'm lame.
|
Sanya12364 Posts
I think we can start by looking when the modulus on 2^N repeats.
First start by expression d as 2^e * m where GCD(m, 2) = 1 and e is a non-negative integer Candidate solutions will when N > e and is some multiple of 2^e. note GCD(m, 2^e) = 1
now when m = 1 we trivial solution N = 2^e
by the Totient theorem will get repetitive modulo on phi(m) because 2^phi(m) % m = 1 repetition is over values less than m and relatively prime to m (multiplied by 2^e)
Now for the totients: for all primes t and positive integer n : phi(t^n) = t^(n-1)* (t-1) for all positive integers p & q where GCD(p,q) = 1 : phi(p*q) = phi(p) * phi(q)
seems to get complicated from here on... hmmm To be continued...
|
I think I may have a solution for the odd numbers:
+ Show Spoiler + for any odd d, N=d-1 will give us the desired result.
With the theorem that lastprime gave us, we see the following: gcd(d,d-1) = 1 2^(d-1) = 1 mod d 2^(d-1) + d-1 = 0 mod d
I'm trying to use this to tackle the even numbers as well, with the idea that any even number d = c*(2^x). However, this is all pointless if my earlier conclusion is incorrect.
|
United States4053 Posts
I think this gets messy only because m could be even, which means we need to split into an odd case and an (even harder) even case, and phi(m) often shares factors with m, so looping by adding phi(m) isn't guaranteed to work.
|
So are all of you guys math majors? This problem looks so intimidating I don't even want to touch it haha.
|
Sanya12364 Posts
On September 10 2010 11:59 Slithe wrote:I think I may have a solution for the odd numbers: + Show Spoiler + for any odd d, N=d-1 will give us the desired result.
With the theorem that lastprime gave us, we see the following: gcd(d,d-1) = 1 2^(d-1) = 1 mod d 2^(d-1) + d-1 = 0 mod d
I'm trying to use this to tackle the even numbers as well, with the idea that any even number d = c*(2^x). However, this is all pointless if my earlier conclusion is incorrect.
Only true for prime numbers.
Even numbers aren't too bad. Just factor out the powers of 2 will be sufficient and that will reduce it to an odd number problem. Maybe I'm missing it but the non-prime odd values are the hardest part to solve.
|
On September 10 2010 12:21 TanGeng wrote:Show nested quote +On September 10 2010 11:59 Slithe wrote:I think I may have a solution for the odd numbers: + Show Spoiler + for any odd d, N=d-1 will give us the desired result.
With the theorem that lastprime gave us, we see the following: gcd(d,d-1) = 1 2^(d-1) = 1 mod d 2^(d-1) + d-1 = 0 mod d
I'm trying to use this to tackle the even numbers as well, with the idea that any even number d = c*(2^x). However, this is all pointless if my earlier conclusion is incorrect.
Only true for prime numbers. Even numbers aren't too bad. Just factor out the powers of 2 will be sufficient and that will reduce it to an odd number problem. Maybe I'm missing it but the non-prime odd values are the hardest part to solve.
Oh I misread the theorem. Back to the drawing board...
|
If you need more hints let me know and I'll post some more hints here.
Edit: I suggested this problem to LastPrime for a little Math Puzzle Time in TL.net, so it'd defeat the purpose of me releasing my solution here. We'll post some harder ones once this is solved. Enjoy~
An easier version of this problem is the following: Every positive integer d divides 2^N - N for some N, in which case the idea of looking at cycles work, i.e. 2, 2^2, 2^(2^2), 2^(2^(2^2)), ... eventually becomes constant mod d for any positive integer d. In fact you can bound the cycle length, and get a rather nice expression for an explicit solution for N in terms of d.
Also, I'm on #math of efnet IRC and freenode, ID: hochs. If you want more lively math chat, I'm there and you can /msg me for some fun
Now back to preparing lecture notes for serre duality and its applications to riemann roch type theorems..
|
The solution is more or less obvious for powers of 2 and when d and phi(d) are relatively prime (which notably includes all primes). It's a little less clear to me how to extend the argument to deal with d and phi(d) having a common factor.
(As an aside, for those of you who like this sort of thing, I highly recommend Project Euler. Good times.)
|
Lol i had this EXACT problem in a Math 135 assignment at the university of waterloo last year
|
On September 10 2010 14:38 Oracle wrote:Lol i had this EXACT problem in a Math 135 assignment at the university of waterloo last year
Oh, is that where it's from? ^^ It's a nice exercise in chinese remainder theorem
|
We may assume by the CRT that d=p^n, with p odd, the case p=2 being trivial. Now by induction, there exist N such that 2^N+N=0 mod phi(d). Write 2^N+N + k phi(d) =0. Then 2^(N+k phi(d)) + (N + k phi(d)) = 2^N+N+k phi(d) = 0 mod p^n. CQFD.
On September 10 2010 13:20 mieda wrote: Now back to preparing lecture notes for serre duality and its applications to riemann roch type theorems..
Nice. Will you use it to prove the Hasse-Weil theorem on the zeta function of algebraic curve? From what I remember you can prove it without the classical proof from Weil with Jacobians by clever user of the Riemann-Roch (the hardest part being the Riemann hypothesis, with Jacobians you have the Rosati involution, here I don't remember how you do it).
By the way I infer from your signature that you are working on Complex Multiplication? That's one of the most beautiful area in Mathematics (according to Hilbert )!
|
|
|
|