M.S. Dousti
Reputation
1,052
Top tag
Next privilege 2,000 Rep.
 Apr 21 accepted Expectation of the fraction a random function covers its range Apr 21 asked Expectation of the fraction a random function covers its range Apr 16 awarded Tumbleweed Apr 9 asked Modular arithmetic involving real numbers Mar 24 revised Help on notation: $\mathbb{Z}/n\mathbb{Z}$ vs. $\mathbb{Z}_n$ added 7 characters in body Mar 22 accepted Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k Mar 22 awarded Yearling Mar 21 comment Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k For p=2 (i.e., when p is not odd), the function f(x) can be 4-to-1 (when k>=3). Can we consider this case as well, using your simple counting argument? Mar 21 comment Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k Thanks a lot. But I think you're actually following Hensel's lemma, without naming it. This is the constructive method which iteratively builds the solutions from the ground up. Mar 21 comment Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k @MXYMXY: Actually, it depends on how deep your studies are in number theory. The proof of lemma, especially when we are not dealing with $p$-adic numbers, seems pretty elementary to me, too. But as I'm going to describe it to some undergrad students, I wanted to check out if there's actually a simpler proof. Mar 21 asked Elementary proof for: If x is a quadratic residue mod p, then it is a quadratic residue mod p^k Mar 20 comment Lower bound for $\phi(n)$: Is $n/5 < \phi (n) < n$ for all $n > 1$? @EricNaslund: Thanks for the response. As I wrote in my comment, I built up my argument around the assumption that "$O(\cdot)$ is positive." If $O\left(\frac{n}{(\log \log n)^2}\right)$ is meant to capture a negative quantity (which is allowed under the definition of big-$O$), then everything adds up. Mar 20 comment Proving a combinatorial identity without double counting Great. I always loved your answers; they're so inspiring! Mar 20 comment Proving a combinatorial identity without double counting Thanks for elaboration. I assume this corresponds to (and further formalizes) counting method 1 in the question, right? Mar 20 comment Proving a combinatorial identity without double counting @AndréNicolas: Could you please elaborate? My understanding is that per each ball, one assigns an indicator r.v., which is 1 is the ball is picked in the sample, and 0 otherwise. Did I get it right? Mar 20 comment Proving a combinatorial identity without double counting +1. This answer taught me a lot, thanks! But I'll wait to see if a more "elementary" answer shows up. Mar 19 revised Proving a combinatorial identity without double counting added 24 characters in body Mar 19 asked Proving a combinatorial identity without double counting Mar 19 comment Lower bound for $\phi(n)$: Is $n/5 < \phi (n) < n$ for all $n > 1$? Sorry to bump an old topic, but I think something doesn't add up (though by my lack of experience, I might be mistaken). The inequality $\varphi(n)\geq \frac{n}{e^{\gamma}\log \log n}$ follows from the theorem you stated, assuming $O(\cdot)$ is positive. But Nicolas proved that this inequality does not hold for infinitely many $n$'s. The correct form of the theorem seems to be $\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}}$, see en.wikipedia.org/wiki/Euler%27s_totient_function#Growth_rate. Feb 23 awarded Popular Question