| 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  )! | ||
| ||
|
|
OSC
CranKy Ducklings
Afreeca Starleague
Light vs Flash
INu's Battles
ByuN vs herO
PiGosaur Cup
Replay Cast
Replay Cast
The PondCast
OSC
Replay Cast
[ Show More ] |
|
|
EPT
