Mathematics desk
< October 8	<< Sep \| October \| Nov >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 9[edit]

US default on 17th Oct[edit]

Does the probability of "US Default on 17th Oct" exists? And if so what is the proper Mathematical way of calculating it? 202.177.218.59 (talk) 01:53, 9 October 2013 (UTC)[reply]

Yes, as argued here all probabilities are quantum mechanical in nature (even what looks like obvious counter examples like betting on digits of pi turn out not to be so upon a precise analysis). So, the probability is in principle well defined by the laws of physics and has a quantum mechanical origin. Count Iblis (talk) 15:04, 9 October 2013 (UTC)[reply]

The people making these estimates presumably use data on daily government spending, and know how much is spent in a day and how much that value varies. From there they can build statistical models of how likely the funds are to run out at any given day. Presumably this is simpler than working from first principles as Count Iblis suggests. :-) I don't want to give too much detail, because it is speculation - maybe someone can track down the source that the 17th date came from originally to see if methodology is given. Katie R (talk) 19:06, 9 October 2013 (UTC)[reply]

According to Time "Economists at JPMorgan have been more precise, estimating that the Treasury will run out of cash on the 24th—one week after Treasury says it’s extraordinary measures will be exhausted. They write that it is “extremely unlikely” the Treasury will be able to make its payments more than a few days after the 24th, and that the Treasury would most certainly have to default on some payments by November 1st, when large outlays for Social Security, Medicare, retirement benefits for military and civil services workers, and interest payments are due." Gandalf61 (talk) 20:04, 9 October 2013 (UTC)[reply]

Common factors of a sum[edit]

This might be a terribly difficult question, given how greatest common divisors behave. Suppose I have two odd integers, A and D, and two even integers, B and C, such that: gcd(A,B,C,D) = 1, but gcd(A,B) ≠ 1 and gcd(C,D) ≠ 1. Does there exist some integer K such that gcd(C + 2KA, D + 2KB) = 1? Searching for a counterexample has proved fruitless - after dozens of attempts, the gcd of the sums has been 1 for K = 1 or K = -1. It seems like there should always be such a K, but I have very little idea of how to show it. Any suggestions are greatly appreciated! Icthyos (talk) 14:02, 9 October 2013 (UTC)[reply]

Let A=3, D=5, B=6, C=10, which fulfil all of your conditions regarding A, B, C, and D.

Let K=2, so that C+2KA=22 and D+2KB=29, and gcd(C + 2KA, D + 2KB) = 1.

(Should K be relatively prime to C and D? Perhaps that helps.)Bh12 (talk) 16:01, 9 October 2013 (UTC)[reply]

Your example certainly works, but I should clarify: I'm wondering if it's possible for there to be A, B, C, D satisfying the above conditions such that there is no integer K for which gcd(C + 2KA, D + 2KB) = 1. For all the examples of A, B, C, D I pick, I can always find some K for which this gcd is 1, but I'm having a hard time proving that there always exists such a K in general. Finding examples is the easy part! Icthyos (talk) 16:15, 9 October 2013 (UTC)[reply]

So let K be prime to A, B, C, and D. Then C+2KA is even and is relatively prime to A. Also, D+2KB is odd and is relatively prime to D, K, and B.

If C+2KA and D+2KB are relatively prime, such a K does exist.

If C+2KA and D+2KB are not relatively prime, double the value of K; if C+2KA and D+2KB are now relatively prime, such a K does exist.

If C+2KA and D+2KB are still not relatively prime, again double the value of K; if C+2KA and D+2KB are now relatively prime, such a K does exist.

I need some help on this last point, but I don't think that K can be doubled more than twice without having gcd(C + 2KA, D + 2KB) = 1.Bh12 (talk) 17:29, 9 October 2013 (UTC)[reply]

What's your reason for this intuition about not having to double K more than twice? Also, I'm not sure I believe: So let K be prime to A, B, C, and D. Then C+2KA is even and is relatively prime to A. -- if A and C have some common factor bigger than 1, then A and C+2KA also have this as a common factor. (Recall, A and C can have a common factor bigger than 1, it just can't be shared in common with both B and D). Icthyos (talk) 19:45, 9 October 2013 (UTC)[reply]

So let K be prime to A,B,C,D, let C+2KA have a gcd GT 1, but that gcd is NOT shared with D+2KB because gcd(A,B,C,D)=1).

Likewise, B and D can have a gcd GT 1, but that gcd is NOT shared with A and C.

C+2KA and D+2KB should then be relatively prime - forget about what I said about doubling K - so that such a K exists.

Or can you provide a counterexample?Bh12 (talk) 20:20, 9 October 2013 (UTC)[reply]

Take A = 5, B = 20, C = 38, D = 19 and K = -1. Then C + 2KA = 28 and D + 2KB = -21, which have gcd 7. The problem is that new divisors can appear in the sums that are not divisors of any of A, B, C or D. Icthyos (talk) 21:13, 9 October 2013 (UTC)[reply]

If you want "some integer K" such that the required gcd=1, then in your example take K=2, so that C+2KA=58 and D+2KB=99. What diference would it make that for K=-1 the gcd is not 1?Bh12 (talk) 00:01, 10 October 2013 (UTC)[reply]

Yes, but the example demonstrates that not any old K will work. A priori, it's entirely possible that there exists A, B, C, D satisfying the conditions, for which there is no K giving the gcd in question to be 1. I want to prove that there is always such a K. Icthyos (talk) 12:35, 10 October 2013 (UTC)[reply]

I think a more general form would be more tractable. Suppose the following statement is true:

Given a, b, c, d, with GCD(a, b, c, d)=1 and ad-bc≠0, then GCD(c+ka,d+kb)=1 for some k.

Let a=2A, b=2B, c=C, d=D in the above problem. D is odd so 2 cannot be a common factor of a, b, c, d, and neither can any other prime else GCD(A, B, C, D) is not 1. Also A and D are odd, and B and C are even, so AD-BC≠0, so ad-bc=2(AD-BC)≠0. So the conditions for the above statement hold which would imply that there is a k so that GCD(c+ka,d+kb)=GCD(C+2kA,D+2kB)=1.

I believe I have a proof of the statement given and I'll post that in a bit. --RDBury (talk) 22:24, 9 October 2013 (UTC)[reply]

(Part 2): To prove the above statement, I claim it's sufficient to prove the special case a=0. Suppose true for a=0, i.e.:

Given b, c, d, with GCD(b, c, d)=1 and b, c≠0, then GCD(c,d+kb)=1 for some k.

First:

Lemma: If ps-qr=1 then GCD(m,n)=GCD(pm+qn,rm+sn) for any m, n.

Proof: If u divides m and n then u divides pm+qn and rm+sn, so GCD(m,n)|GCD(pm+qn,rm+sn). Also s(pm+qn)-q(rm+sn)=m and -r(pm+qn)+p(rm+sn)=n. So if u divides pm+qn and rm+sn then u divides m and n, so GCD(pm+qn,rm+sn)|GCD(m,n). Therefore GCD(m,n)=GCD(pm+qn,rm+sn) as required.

Let a, b, c, d be given with GCD(a, b, c, d)=1, and ad-bc≠0. Let GCD(a,b)=e, there are x and y so that ax+by=e. Then (a/e)x+(b/e)y=1. Apply the lemma to get GCD(c+ka,d+kb)=GCD((b/e)(c+ka)-(a/e)(d+kb),x(c+ka)+y(d+kb))=GCD((ad-bc)/e,xc+yd+k(ax+by))=GCD((ad-bc)/e,xc+yd+ke). Let c'=(ad-bc)/e, d'=xc+yd, b'=ax+by. GCD(c',d')=GCD(c,d) by the lemma, and b'=e=GCD(a,b). So GCD(b',c',d')=GCD(GCD(a,b),GCD(c,d))=GCD(a,b,c,d)=1. Both b'=e and c'=(ad-bc)/e are nonzero so there is a k so that GCD(c',d'+kb')=GCD(c+ka,d+kb)=1.

If remains so show the a=0 which I will post next. --RDBury (talk) 00:47, 10 October 2013 (UTC)[reply]

Wow, thanks for taking the time to explain this so carefully. I followed this up until the final step. We know that GCD(b',c',d') = 1, so we can find integers f, g, h so that fb' + gc' + hd' = 1, and so 1 = h(d' + (f/h)b') + gc'. Taking k = f/h, we then know GCD(c',d'+kb') = 1...but how do we know that f/h is an integer? Or are you arguing this step in another way? Icthyos (talk) 12:35, 10 October 2013 (UTC)[reply]

Oh wait, I see, we're using our assumption that it's true when a = 0. Clever! Icthyos (talk) 12:46, 10 October 2013 (UTC)[reply]

(Part 3). It remains to show, if GCD(b,c,d)=1, and b, c≠0, then GCD(c,d+kb)=1 for some k. First, let c' be the product of the prime factors of c. Then c' divides c so GCD(b,c',d)=1 and if p divides c and d+kb then it divides c' and d+kb. So if there is a k so that GCD(c',d+kb)=1 then GCD(c,d+kb)=1. So we can assume without loss of generality that c is square free.

Suppose c and d have a common prime factor p. Let c=c'p. Since c is square free, p does not divide c'. Suppose also there is k so that GCD(c',d+kb)=1. If p divides k then replace k with k+c', GCD(c',d+(k+c')b)=GCD(c',d+kb+c'b)=GCD(c',d+kb)=1 so this can be done. Suppose c and d+kb have a common prime factor q. If q=p, then since p divides c and d, p divides kb. But p does not divide k so p divides b, contradicting the assumption that that GCD(b, c, d)=1. So q ≠ p. Then q divides c' and d+kb contracting GCD(c',d+kb)=1. So if there is k so that GCD(c',d+kb)=1 then there is k so that GCD(c,d+kb)=1. So we can assume that c and d are relatively prime. But in this case simply take k=0 to get the result. --RDBury (talk) 01:29, 10 October 2013 (UTC)[reply]