| 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  )! | ||
| ||
StarCraft 2 StarCraft: Brood War Dota 2 League of Legends Counter-Strike Heroes of the Storm Other Games |
|
Sparkling Tuna Cup
INu's Battles
herO vs Classic
Percival vs Rogue
Shopify Rebellion Sundays
MilkiCow vs TBD
Clem vs TBD
BSL Open Qualifier
BSL Open Qualifier
Replay Cast
Afreeca Starleague
Rush vs Light
WardiTV Weekly
Monday Night Weeklies
Replay Cast
[ Show More ] |
|
|
EPT
