Stuff about BonusQuestion

BonusQuestion’s awards

Comments

April 21st, 2009

LostInParadise said :

Regarding your answer:
Thanks for the proof. I will have to go over it when I come home from work.

March 6th, 2009

finkelitis said :

BonusQuestion: Great use of Pell’s equation! You totally did me a service here—I wasn’t expecting anyone on fluther to be able to answer that question for me, and not only did you answer it, but you obviously put some time in, and came up with a simple, elegant solution. Also, you happen to have answered another issue for me (I was dealing with the d=0 case in another context also). Thanks a lot for your thoughtful work on my problem.

February 25th, 2009

LostInParadise said :

Regarding your answer:
I really appreciate the time that you put into the analysis of the problem. The realization that the problem was equivalent to x^1/x = y^1/y is something that I missed.

May 21st, 2008

marissa said :

Good to see you friend!

Questions

• March 9th, 2009

  Are you interested in a fun math problem? Take a look!

  Great Question (0)
• October 18th, 2008

  Is this the new low for McCain?

  Great Question (1)
• September 22nd, 2008

  Minnesota Political Junkies: can you give me some information regarding the Senate race?

  Great Question (1)
• September 20th, 2008

  Could his race cost Obama the election?

  Great Question (3)
• September 9th, 2008

  Do you think Fluther is dominated by Liberals?

  Great Question (1)

Browse all of BonusQuestion's questions…

Answers

• August 5th, 2009

  Can anyone help me with a technical mathematical divisibility issue?

  The proof of the claim goes like this: Let p be any prime of the form 4dn+1. Then if q is a prime factor of d we have: (p/q) (q/p) = (-1)^ {(p-1)*(q-1)/4} (This is where I use reciprocity law.) Now since p = 1 (mod 4) RHS of the above equality is 1. And since p = 1 (mod q) we have (p/q) = 1. Which means (q/p) = 1 for any prime factor of d. But since Legendre symbol is multiplicative (d/p) = 1 for any prime p of the form 4dn+1.
  Great Answer (1)
• August 5th, 2009

  Can anyone help me with a technical mathematical divisibility issue?

  First a little claim that needs proof but I am pretty sure it is easy to prove. (I think it should be proved with the reciprocity law .) Claim: For any natural number d there is infinitely many primes p such that (d/p) = 1 where (d/p) is the Legendre symbol. Now let p be a prime, x an integer such that x^2 = d (mod p). If we multiply both sides by (the inverse of x mod p)^2, say y, we get d y^2 = 1 (mod p). Obviously we can take y to be between 1 and p/2. We have d y^2 -1 = p s for some natural number s. Now if d y^2 – 1 is not divisible by p^2, take: r = p & k = y and we are done. Now assume dy^2–1 is divisible by p^2. Take r = p and k = p-y. We have: d k^2 – 1 = d (p-y)^2 – 1 = d y^2 – 1 – 2d y p + d p^2 = 0 – 2dyp + 0 (mod p^2) But 2dy is not divisible by p so, dk^2 – 1 is not divisible by p^2. Which means if we set dk^2 – 1 = rs, then s is not divisible by r. On the other hand k = p-y < p = r.
  Great Answer (2)
• May 23rd, 2009

  Any Obama supporters want to defend his recent statements calling for a new legal regime to support "Prolonged & Preventive Detention?"?

  Dale? Are you there? :D
  Great Answer (0)
• May 4th, 2009

  Brain Teaser - Can you complete this proof that everyone (yes, including you) ought to know?

  I was looking at wikipedia article about Euclid Numbers. It says ”A Euclid number can not be a perfect square.” Perhaps one of us should add that it cannot be the m-th power for any m>1. :)
  Great Answer (0)
• April 21st, 2009

  Brain Teaser - Can you complete this proof that everyone (yes, including you) ought to know?

  It appears that I cannot show a is not m-th power of any integer. However I can still show it is not m-th power of pi. (Which is what I need for my previous claim). In just the last step I need to assume x=pi. So I don’t assume x=pi until the very last line of the argument. The proof is a bit long. So I am trying to break that into a few steps. First lets prove this lemma. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Lemma. Let p and q be two prime numbers, x and m be two positive integers such that x^m – 1 is divisible by q and m is divisible by p. Then one of the following two cases occures. 1) x^(m/p) = 1 (mod q) 2) p divides q-1 Proof of this lemma goes like this: m is divisible by p. So if we let b = x^(m/p), this is an integer and b^p – 1 is divisible by q. On the other hand, by Fermat’s Little Theorem, we know that b^(q-1) – 1 is divisible by q. Now if r is g.c.d. of p and q-1, since we can write r as a linear combination of p and q-1 and then use the following two facts: b^p = 1 (mod q) & b^(q-1) = 1 (mod q) And deduce that: b^r = 1 (mod q). Now, since r divides p it is either 1 or p. 1) r=1, by the above equation we have b = 1 (mod q) which is what we wanted to prove. 2) r=p. This means p divides q-1 which is the other case of the Lemma. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Now, back to the original statement. Let a = (the product of p1,..., pk excluding pi) + 1 = x^m. Therefore we have x^m = 1 (mod pj) for j <= k and j <> i. Since m > 1, it has a prime factor p. Now I am trying to show this is impossible by checking different assumptions on p. Case 1) p > pk. We have x^m = 1 (mod pj). By lemma either p divides pj – 1 or x^(m/p) = 1 (mod pj). But since pj – 1 is less than p, the first case is impossible. Therefore x^(m/p) = 1 (mod pj). Hence x^(m/p) – 1 is divisible by (the product of p1,..., pk excluding pi) which was a – 1 = x^m -1. This is a contradiction, because x^(m/p)-1 is less than x^m – 1. Case 2) p = pj for some j < k and j<>i. Since p is one of pj’s, we have x^m = 1 (mod p) and p divides m. Therefore, by Lemma, either p divides p-1 or x^(m/p) = 1 (mod p). The first one is impossible so x^(m/p) = 1 (mod p). But if you take y = x^(m/p) then we have x^m – 1 = y^p – 1 = (y-1) (y^(p-1)+....+y+1). Since y = 1 (mod p) for the second expression we have: (y^(p-1)+....+y+1) = 1+1+...+1 = p = 0 (mod p). Hence (y^(p-1)+....+y+1) is divisible by p. Therefore y^p-1 is divisible by p^2. So x^m – 1 is divisible by p^2. But x^m-1 is square free which is a contradiction. Case 3) p=pi (This is the same i that we excluded from the product.). The above arguments showed that all of prime factors of m are pi. So we can assume m = pi^l. Now I know x^m = 1 (mod pj) for any j <= k and j<>i. So by Lemma either pi divides pj-1 or x^(m/pi) = 1 (mod pj). If we only look at j < i, the first case cannot occure. So we have x^(m/pi) = 1 (mod pj) for j < i. Repeat this argument and we can reduce the exponent of x, which is m/pi to m/pi^2. Repeating this argument we can finally get rid of m and get x = 1 (mod pj). Which means x – 1 is divisible by p1…p(i-1) It appears that only for this part of my argument I need to assume x = pi. If x=pi this cannot happen as one can pretty easily show pi < p1….p(i-1)+1. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ This is a variation of the proof presented in the following article. (I thought I could drop the condition x=pi by modifying the proof, but apparently I can’t!) Cosgrave, John B. A remark on Euclid’s proof of the infinitude of primes. Amer. Math. Monthly 96 (1989), no. 4, 339—341. If you have access to JSTORE here is the direct link to the article: http://www.jstor.org/stable/2324090 P.S. This argument shows that p1…pk + 1 (which is sometimes called Euclid’s number) cannot be the m-th power of any number.
  Great Answer (1)

Browse all of BonusQuestion's answers…