Timeline for Cycle Length of the Positive Powers of Two Mod Powers of Ten [closed]
Current License: CC BY-SA 2.5
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 28, 2013 at 12:48 | history | closed |
Ricardo Andrade Andrey Rekalo Olivier Benoist Stefan Kohl♦ Willie Wong |
Not suitable for this site | |
| Nov 28, 2013 at 8:03 | review | Close votes | |||
| Nov 28, 2013 at 12:48 | |||||
| Nov 9, 2009 at 16:57 | vote | accept | Rick Regan | ||
| Nov 9, 2009 at 16:56 | answer | added | Rick Regan | timeline score: -1 | |
| Oct 23, 2009 at 14:30 | answer | added | Qiaochu Yuan | timeline score: 3 | |
| Oct 23, 2009 at 14:27 | comment | added | Qiaochu Yuan | Sorry, I meant "if and only if a_n = a_m." | |
| Oct 23, 2009 at 14:24 | comment | added | Qiaochu Yuan | Because CRT is bijective and b_n is eventually constant, for all but finitely many n we have CRT(a_n, b_n) = CRT(a_m, b_m) if and only if n = m, hence the period of CRT(a_n, b_n) is equal to the period of a_n. Again, there's nothing deep going on here; bijections preserve period. | |
| Oct 22, 2009 at 16:05 | comment | added | Rick Regan | "What is the period of CRT(a_n, b_n)?" -- that's the million dollar question. The answer seems "obvious," but if you were writing a proof, say ANSWERING a mathoverflow question that people would vote on for best answer -- what would you write? Are you using LCMs? A result from group theory? I'm looking for something concrete. | |
| Oct 22, 2009 at 7:08 | comment | added | Qiaochu Yuan | All you need to know is that there exists a bijective function CRT(a, b) which given a residue mod 2^k and a residue mod 5^k spits out a unique residue mod 10^k. Now you have a sequence CRT(a_n, b_n) with the property that a_n is periodic with period 4*5^{m-1} and b_n is eventually constant. What is the period of CRT(a_n, b_n)? (There is nothing deep going on here.) | |
| Oct 21, 2009 at 16:37 | comment | added | Rick Regan | OK, so the powers of 2 mod 2^m cycle with period 1 (starting at 2^m), and the powers of 2 mod 5^m cycle with period 4*5<sup>m-1</sup>. To get the powers of 2 mod 10^m, the answer seems to be to multiply the two periods: 1 x 4*5<sup>m-1</sup> = 4*5<sup>m-1</sup>. But what specifically about the CRT lets me do that? The statements of the CRT I've seen talk about the residues, not the periods. Maybe I need to invoke an underlying theorem from group theory instead? | |
| Oct 18, 2009 at 13:33 | comment | added | Rick Regan | Sure I can use the CRT for the individual cases. For example, the powers of two mod 5 are 2, 4, 3, 1. I can set up four pairs of equations: x==2 mod 5 and x==0 mod 2, x==4 mod 5 and x==0 mod 2, x==3 mod 5 and x==0 mod 2, and x==1 mod 5 and x==0 mod 2. This gives 2, 4, 8, 6 mod 10, respectively -- a cycle of 4. How do I generalize to mod 5^k and mod 2^k? | |
| Oct 18, 2009 at 0:05 | comment | added | Rick Regan | Alon: it varies by k Qiaochu: sorry, I don't "know" either of those points yet. That is my question! (BTW, I'm not a student doing a homework assignment) | |
| Oct 17, 2009 at 23:02 | comment | added | Qiaochu Yuan | You mean eventually zero. Now you know that the residue mod 5^m and the residue mod 2^m uniquely determines the residue mod 10^m by CRT, and you know that one is periodic and the other is eventually constant. What can you conclude? | |
| Oct 17, 2009 at 22:59 | comment | added | Alon Amit | So if M is a number which leaves a residue of 1 mod 5^k, and a residue of 0 mod 2^k, what residue does it leave mod 10^k? | |
| Oct 17, 2009 at 22:02 | comment | added | Rick Regan | Their ''period'' would always be 1 (powers are always 0). | |
| Oct 17, 2009 at 21:26 | comment | added | Qiaochu Yuan | You know that the powers of two have a certain period mod 5^m. What is their period mod 2^m? | |
| Oct 17, 2009 at 20:04 | comment | added | Rick Regan | Could you elaborate please? | |
| Oct 17, 2009 at 19:19 | comment | added | Qiaochu Yuan | It's exactly the Chinese Remainder Theorem. | |
| Oct 17, 2009 at 19:14 | history | asked | Rick Regan | CC BY-SA 2.5 |