| Blogs > LastPrime |
|
LastPrime
United States109 Posts
Prove that for any positive integer d,there is an integer N for which d| 2^N+N. (means d divides 2^N+N evenly) edit: + Show Spoiler + 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 Hall of Fame 1. Steve496  | ||
|
Hidden_MotiveS
Canada2562 Posts
I give up edit: working on it. | ||
|
BottleAbuser
Korea (South)1888 Posts
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... | ||
|
Seth_
Belgium184 Posts
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 | ||
|
BottleAbuser
Korea (South)1888 Posts
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... | ||
|
Exteray
United States1094 Posts
| ||
|
BottleAbuser
Korea (South)1888 Posts
| ||
|
LastPrime
United States109 Posts
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! | ||
|
Slithe
United States985 Posts
I'll probably give it a bit of a shot and give up because I'm lame. | ||
TanGeng
Sanya12364 Posts
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... | ||
|
Slithe
United States985 Posts
+ 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. | ||
infinitestory
United States4053 Posts
| ||
|
Snuggles
United States1865 Posts
| ||
|
TanGeng
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. | ||
|
Slithe
United States985 Posts
On September 10 2010 12:21 TanGeng wrote: 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... | ||
|
mieda
United States85 Posts
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.. | ||
|
Steve496
United States60 Posts
(As an aside, for those of you who like this sort of thing, I highly recommend Project Euler. Good times.) | ||
|
Oracle
Canada411 Posts
 | ||
|
mieda
United States85 Posts
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 | ||
|
gondolin
France332 Posts
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  )! | ||
|
Steve496
United States60 Posts
| ||
|
mieda
United States85 Posts
On September 10 2010 15:30 gondolin wrote: 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. 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 )!Riemann Roch is useful for just about everything involving curves (ofc there is an analogue for surfaces.. but the formulas get nasty when dimensions rise)! I'm preparing the notes as a background for students who are starting to count dimensions of automorphic forms of various weights. They'll need to know some dimension theory on the complex surfaces formed from congruence subgroups, and that's just riemann roch ^^. Actually you don't need serre duality for proof of riemann roch theorems, especially if one is only working over the complexes, but the idea is nice enough I'm not really working on complex multiplication per se. That's more lower dimension (i.e. elliptic curves). Of course there are analogues for higher dimensional abelian varieties, but the thing I work on is nice combinatorial descriptions (if I can!) of cohomology of rapoport-zink spaces. Also, you should probably fill in more detail for reduction to d = p^n case. Chinese Remainder Theorem directly doesn't apply, as you will see. The problem is that the modulus are not pair-wise coprime when you apply it directly. But it just takes a little more work to get it to work. Are you working on math also? | ||
|
mieda
United States85 Posts
On September 10 2010 15:36 Steve496 wrote: Why does CRT force d=p^n? It doesn't, not directly at least. You still need to work a little bit to reduce to the d = p^n case. The moduli are not pair-wise coprime when you try to apply it directly, but just takes a little more massage to get it to work. | ||
|
mieda
United States85 Posts
Other nice problem | ||
|
gondolin
France332 Posts
On September 10 2010 15:43 mieda wrote: Riemann Roch is useful for just about everything involving curves (ofc there is an analogue for surfaces.. but the formulas get nasty when dimensions rise)! I'm preparing the notes as a background for students who are starting to count dimensions of automorphic forms of various weights. They'll need to know some dimension theory on the complex surfaces formed from congruence subgroups, and that's just riemann roch ^^. Actually you don't need serre duality for proof of riemann roch theorems, especially if one is only working over the complexes, but the idea is nice enough Yes, the "nice" generalisation is Grothendieck-Riemann-Roch, but it is harder to expose (But I still find it beautiful that Riemann-Roch is a relative theorem) I'm not really working on complex multiplication per se. That's more lower dimension (i.e. elliptic curves). Of course there are analogues for higher dimensional abelian varieties, but the thing I work on is nice combinatorial descriptions (if I can!) of cohomology of rapoport-zink spaces. Well Complex Multiplication on elliptic curves is known since Kronecker. (The fact that the j-invariant give the Hilbert class field of Imaginary Quadratic fields). The work of Shimura was to generalize this to abelian varieties. (The modular invariants of an abelian variety with CM by K lies in the Hilbert class field of the reflex field + the reciprocity law expressing the action of the Galois group in term of the type norm of the ideals of the reflex field.) Also, you should probably fill in more detail for reduction to d = p^n case. Chinese Remainder Theorem directly doesn't apply, as you will see. The problem is that the modulus are not pair-wise coprime when you apply it directly. But it just takes a little more work to get it to work. Are you working on math also? Yeah that's true, you need to keep track of the congruent relations of the N_i solution for p_i to verify you can "glue" the solutions. (That's funny how the point of view change, before I thought of the CRT as an arithmetic statement, now when I think about it I visualize it as local sections over Spec(Z/NZ) that we try to glue). I have a background in mathematics, but now I am working on computer science By the way I see that you are from Harvard. Do you know Sophie Morel? She attended the same "college" as me and is very good | ||
|
mieda
United States85 Posts
Yeah that's true, you need to keep track of the congruent relations of the N_i solution for p_i to verify you can "glue" the solutions. (That's funny how the point of view change, before I thought of the CRT as an arithmetic statement, now when I think about it I visualize it as local sections over Spec(Z/NZ) that we try to glue). Yea, that's actually a nice way to visualize it. I have a background in mathematics, but now I am working on computer science By the way I see that you are from Harvard. Do you know Sophie Morel? She attended the same "college" as me and is very good Oh good. Yes, of course I know Sophie Morel, she's a new professor here. But I don't see her here nowadays. I presume she's visiting IAS now with the big number theory thing going on there this year. It's interesting to see another person who did math in TL.net ^^. | ||
|
gondolin
France332 Posts
It's interesting to see another person who did math in TL.net ^^. Did you play SC also? There is a user (Muirhead I think) that is also doing math (he works on algebraic geometry in MIT). Yeah I discovered SC when I went to the "college" I mentioned. I played warcraft 3 before, but once I discovered SC i switched | ||
|
Ivs
Australia139 Posts
Fixing any a, d, k, and gcd(d,k)=1 ka^x = x mod d always has infinitely many solutions x. Proof: + Show Spoiler + let x=ka^y mod d then all we need to do is to find infinitely many y satisfying a^(ka^y) = a^y mod d But since for any a, powers of a in mod d eventually cycles in period phi(d), it is sufficient to find infinitely many solutions to ka^y = y mod phi(d) now phi(d)<d so this is the same problem in a smaller mod. The result is certain true for d=1, induction cleans up the rest. Setting a=2, k=-1 solves your question =). | ||
Plexa
Aotearoa39261 Posts
On September 10 2010 17:21 gondolin wrote: There is a user (Muirhead I think) that is also doing math (he works on algebraic geometry in MIT). Yeah I discovered SC when I went to the "college" I mentioned. I played warcraft 3 before, but once I discovered SC i switched And I just finished my undergrad in Math! Yay! Now doing some work in Topology :3 | ||
|
mieda
United States85 Posts
On September 10 2010 21:08 Ivs wrote: There is a generalisation to this: Fixing any a, d, k, and gcd(d,k)=1 ka^x = x mod d always has infinitely many solutions x. Proof: + Show Spoiler + let x=ka^y mod d then all we need to do is to find infinitely many y satisfying a^(ka^y) = a^y mod d But since for any a, powers of a in mod d eventually cycles in period phi(d), it is sufficient to find infinitely many solutions to ka^y = y mod phi(d) now phi(d)<d so this is the same problem in a smaller mod. The result is certain true for d=1, induction cleans up the rest. Setting a=2, k=-1 solves your question =). The problem is that x = ka^y mod d doesn't imply a^(ka^y) = a^x (mod d). | ||
|
Ivs
Australia139 Posts
On September 11 2010 00:23 mieda wrote: The problem is that x = ka^y mod d doesn't imply a^(ka^y) = a^x (mod d). I didn't say it implies, rather, it is suffice to solve the second equation to obtain a solution to the first. edit: More specifically, If x = ka^y, then ka^x = x mod d if and only if a^(ka^y) = a^y mod d | ||
|
mieda
United States85 Posts
On September 11 2010 00:55 Ivs wrote: I didn't say it implies, rather, it is suffice to solve the second equation to obtain a solution to the first. edit: More specifically, If x = ka^y, then ka^x = x mod d if and only if a^(ka^y) = a^y mod d Sure, but when k < 0 you're raising a to a negative power. For example in our case a = 2 and k = -1, you're saying -2^x = x (mod d) iff 2^(-2^y) = 2^y mod d, and how will you interpret 2^(-2^y) ? it's not an integer. Also, in your original proof you wrote x = ka^y (mod d), thus sufficient to solve a^(ka^y) = a^y mod d, from which I thought that you seemed to be saying that if x = ka^y (mod d) then a^x = a^(ka^y) mod d, which isn't true. Remark: When k > 0, the remark I made earlier in this thread is exactly this method. This solution doesn't seem to work, because we have k < 0 now. I made the remark that when we have to solve 2^N = N (mod d) and not 2^N = -N (mod d), then it's a bit easier. Edit: There is a way to fix this argument, and that is to choose k so that gcd(d,k) = 1 and k > 0 by adding d to it sufficient number of times. | ||
|
KristianJS
2107 Posts
| ||
|
mieda
United States85 Posts
On September 11 2010 02:23 KristianJS wrote: This exercise taught me a useful lesson in how the normal conditions given for CRT are stronger than necessary The exercise has served its purpose! | ||
|
Ivs
Australia139 Posts
On September 11 2010 02:07 mieda wrote: Sure, but when k < 0 you're raising a to a negative power. For example in our case a = 2 and k = -1, you're saying -2^x = x (mod d) iff 2^(-2^y) = 2^y mod d, and how will you interpret 2^(-2^y) ? it's not an integer. Also, in your original proof you wrote x = ka^y (mod d), thus sufficient to solve a^(ka^y) = a^y mod d, from which I thought that you seemed to be saying that if x = ka^y (mod d) then a^x = a^(ka^y) mod d, which isn't true. Remark: When k > 0, the remark I made earlier in this thread is exactly this method. This solution doesn't seem to work, because we have k < 0 now. I made the remark that when we have to solve 2^N = N (mod d) and not 2^N = -N (mod d), then it's a bit easier. Edit: There is a way to fix this argument, and that is to choose k so that gcd(d,k) = 1 and k > 0 by adding d to it sufficient number of times. I did impose gcd(d,k) = 1, read the whole thing =P. You are right about the negative part though, and yup it is easily fixed. | ||
|
mieda
United States85 Posts
I did impose gcd(d,k) = 1, read the whole thing =P. You are right about the negative part though, and yup it is easily fixed. I read the whole thing. Only the $k > 0$ is meant to be new. You should read my last sentencen as "gcd(d,k) = 1" *and also* "k > 0" | ||
|
Ivs
Australia139 Posts
On September 11 2010 11:36 mieda wrote: I read the whole thing. Only the $k > 0$ is meant to be new. You should read my last sentencen as "gcd(d,k) = 1" *and also* "k > 0" Oh right, fair enough (=. | ||
| ||
StarCraft 2 StarCraft: Brood War League of Legends Counter-Strike Super Smash Bros Other Games |
|
WardiTV Spring Champion…
Zoun vs Classic
herO vs Clem
Solar vs MaxPax
Big Brain Bouts
Epic vs Mixu
Spirit vs Jumy
WardiTV Invitational
Replay Cast
SOOP
GSL Qualifier
WardiTV Spring Champion…
ByuN vs TriGGeR
SC Evo League
BSL Season 20
DragOn vs OctZerg
Artosis vs Doodle
Replay Cast
[ Show More ] |
|
|
EPT
