Consider all of the residues modulo 20. Given any one of those residues, can you always find a multiple of 7 that leaves that residue modulo 20?
The solution to this is fairly simple. In fact, the simple solution to this did not occur to me until I proved a generalization of the statement. Regardless, I will show that solution here first for demonstration purposes. In the case of 7, it is immediately apparent that \(21\equiv1\pmod{20}\). So if we desire to produce the residue \(k\), just take \(3k\cdot 7\). There it is. Simple, right? In fact, not only is it simple, but it's a bit cheap. It doesn't really tell us what's going on under the hood. We just conveniently found a multiple of 7 that was congruent to 1 modulo 20. So let's walk away from the specificity of the numbers 7 and 20 and instead pose the following problem. Let \(m,n\in\mathbb{N}\) be coprime, with \(m<n\). Given any residue modulo \(n\), can one always find a multiple of \(m\) that leaves that residue modulo \(n\)? Obviously, if we can show that there exists a multiple of \(m\) congruent to 1 modulo \(n\), we're done. But it wasn't obvious to me how to proceed with this idea that worked very quickly for 7 and 20, for general \(m\) and \(n\). And anyway, the idea with 21 only came to me after I had already solved this problem. Instead, the first thing I saw here is that we only need to work with multiples of \(m\) up to \(mn\). This is because \(m(n+r)\equiv mr\pmod{n}\). This is actually the first solution I presented to the original problem with 7 and 20. Just check all of the multiples of 7 up to 140. Of course this isn't as efficient as the observation of \(3k\cdot7\). So let \(A=\{m,2m,\ldots,mn\}\). From this set, the first thing I observed was that the first half of the set cancelled with partners reflected across the middle into the last half of the set, modulo \(n\). For instance, \(m+m(n-1)\equiv0\pmod{n}\). But this still didn't answer the question. Because there was no indication that when we look through the pairings, every residue was covered. This made me wonder how much room I had for overlapping residues. It turns out, conveniently, that the answer to that question is "none". Observe that the set of residues modulo \(n\) is \(B=\{0,1,\ldots,n-1\}\). More importantly, \(|A|=|B|=n\). Now we're going somewhere! By the pigeonhole principle, the answer to our question is "yes" if and only if each multiple in \(A\) gives a unique residue modulo \(n\). Obviously \(mn\) takes care of the residue 0. Since \(m\) and \(n\) are coprime, no other element of \(A\) leaves that residue of 0. So now, excluding \(mn\), let us take two elements of \(A\), say \(km\) and \(jm\). Suppose, to the contrary, that they do leave the same residue modulo \(n\). Then \(km\equiv jm\pmod{n}\). Since \(m\) and \(n\) are coprime, we have \(\gcd{(m,n)}=1\) so we can divide the congruence by \(m\) to obtain \(k\equiv j\pmod{n}\). But this is a contradiction! Because \(0<k<j<n\) or \(0<j<k<n\). So the answer to our question is "yes".
0 Comments
The summer has arrived and I'm back in Florida! Let us begin with a cutie.
Problem: Consider the number \[k(n)=1\underbrace{4...4}_{\text{$n$ digit $4$'s}}.\] For what values \(n\) is \(k(n)\) a perfect square? Solution: \(k(0)\) is obviously a perfect square and \(k(1)\) is obviously not. For \(n>1\), we have that \(k(n)\) is even, since it ends with the digit 4. Any even square is divisible by 4. By long division, we find that for \(n>1\), \[\frac{k(n)}{4}=36\underbrace{1...1}_{\text{$n-2$ digit $1$'s}}.\] So it suffices to find the \(n\) for which this number is a square. Observe that squares are congruent to either 0 or 1 modulo 4 (if you've stuck around here for some time, you'd notice that we LOVE taking squares modulo 4). But, by long division, we see that \(\frac{k(n)}{4}\) is congruent to 3 modulo 4 whenever \(n>3\). So, we need to only check \(n=2\) and \(n=3\). Indeed, \(144=12^2\) and \(1444=38^2\). So \(k(n)\) is square precisely when \(n\in\{0,2,3\}\). \(\square\) I have a few ideas about what I plan on doing next here. I want to talk about Lebesgue integration. The theory of Riemann integration that we thoroughly developed in MATH 31CH is a powerful conceptual tool, but it has several weaknesses. For example, the Riemann integral is not well-defined over \(\mathbb{R}^n\) for functions with unbounded supports. The Lebesgue integral allows us to integrate over unbounded supports. This is just one of the advantages it gives. The Lebesgue integral is also considerably more well-behaved under limits, and we'll see that this gives rise to the dominated convergence theorem (DCT), regarding the interchangeability of integrals and limits (which is something that many of us take for granted *cough*MAO heuristics*cough*). This can be extended even further to talk about the interchangeability of differentiation and integration when they are composed on a function. Yes, that's right. The theory of Lebesgue integration is what forms the rigorous underpinnings of Feynman's trick! I will be going through these topics soon, in a main page post. I like this idea, because it sort of pulls together a bunch of stuff that I've seen or worked on for the past few weeks (my final project in MATH 31CH was on Lebesgue integration and Feynman's trick, which a homework problem in physics happened to use, and I also recently stumbled into a problem where one needs to apply DCT). I don't expect that I'll be proving certain things, such as DCT itself and the existence of the Lebesgue integral, because the proofs are quite technical, and honestly you'd be better off reading a textbook if you're looking for those. Instead, I will try my best to show the motivation behind the Lebesgue integral and its utility in approaching problems that are pretty much intractable with Riemann's theory. I should have more time to work on this now. After all, UCSD decided to cancel one of my summer classes (MATH 120A).... Suppose that the \(n\)th prime number is given by \(p_n\) and the number of primes that do not exceed \(n\) is \(\pi(n)\). Let two functions \(f\) and \(g\) be asymptotic to each other, denoted by \(f\sim g\), iff \(\lim_{x\rightarrow\infty}{\frac{f(x)}{g(x)}}=1\). The prime number theorem states
\[\pi(x)\sim \frac{x}{\log{x}}.\] This statement happens to be equivalent to \(p_n\sim x\log{x}\). I will show this equivalence, using the argument made in An Introduction to the Theory of Numbers, though with much of the gaps and leaps in reasoning filled in by myself. The first thing to note is that \(p_n\) and \(\pi(n)\) are inverse functions. That is, \(\pi(p_n)=n\) and \(p_{\pi(n)}=n\). Now, we consider the function \[y=\frac{x}{\log{x}}.\] Taking the logarithm of both sides, we obtain, \[\log{y}=\log{x}-\log{\log{x}}.\] Now, we show that \(\log{\log{x}}=o(\log{x})\). By L'Hôpital's rule, \[\lim_{x\rightarrow\infty}{\frac{\log{\log{x}}}{\log{x}}}=\lim_{x\rightarrow\infty}{\frac{1}{\log{x}}}=0,\] as desired. So now, we can divide the logarithm of \(y\) by the logarithm of \(x\) to obtain \[\frac{\log{y}}{\log{x}}=1-\frac{\log{\log{x}}}{\log{x}}.\] In the limit, this approaches 1, so that \(\log{y}\sim \log{x}\). Hence, when we have \[x=y\log{x},\] we have that the LHS is the inverse of \(y\), but \(\log{x}\) is asymptotic to \(\log{y}\), so the inverse of \(y\) is asymptotic to \(y\log{y}\). Now, it suffices to show that for two divergent functions \(f\sim g\), we must also have \(f^{-1}\sim g^{-1}\). Observe that \[f^{-1}(f(x))=x\Rightarrow\lim_{x\rightarrow\infty}{\frac{f^{-1}(f(x))}{x}}=1.\] Likewise, we have \[\lim_{x\rightarrow\infty}{\frac{g^{-1}(g(x))}{x}}=1.\] But since \(f\sim g\), we can replace \(g\) with \(f\) in the limit to obtain \[\lim_{x\rightarrow\infty}{\frac{g^{-1}(f(x))}{x}}=1.\] Dividing our two limits, we obtain \[\lim_{x\rightarrow\infty}{\frac{f^{-1}(f(x))}{g^{-1}(f(x))}}=1,\] and since \(f\) is divergent, we can write this as \[\lim_{f(x)\rightarrow\infty}{\frac{f^{-1}(f(x))}{g^{-1}(f(x))}}=1,\] so \(f^{-1}\sim g^{-1}\), as desired. Hence, since \(\pi(n)\sim y\), the inverse of \(y\) is asymptotic to \(n\log{n}\), and \(p_n\) is the inverse of \(\pi(n)\), we have \[\boxed{p_n\sim n\log{n}}.\] My first Putnam is over and I solved two of the problems. They are probably not the best written solutions. I am usually quite elaborate when I am able to type solutions, but the problem is the Putnam is timed. And written. Here is one of the problems that I solved.
2019 A1: Determine all possible values of the expression \[A^3+B^3+C^3-3ABC\] where \(A\), \(B\), and \(C\) are nonnegative integers. Solution: My first thoughts:
I messed around with a few representations of the expression with \((A+B+C)^3\). But then I asked myself what is the point? What am I trying accomplish? I needed to find the types of numbers that the expression could be. How could I even characterize that? Clearly, they must be integers, and by AM-GM, they must be nonnegative integers. What characteristics were they expecting me to use to describe the range? Prime or composite? Number of factors? Divisibility? Divisibility seemed to be the natural answer, and I prepared myself for some modular arithmetic. But now what? Time to generate numbers I suppose. I won't pain you through all the computations but what was very insightful is the manner in which I generated the triples. I fixed \(A\), and then let \(B\) and \(C\) run through the nonnegative integers less than or equal to \(A\). Once I ran through all unique combinations (permutations don't matter because the expression is symmetric in all three variables), I incremented \(A\) and repeated the process. I noticed that I was sometimes hitting on the same number twice, but it seemed that letting \(B\) and \(C\) be numbers that were either equal to \(A\) or one less than \(A\) always generated a new number. Let's try this out. Suppose that WLOG \(A=B=n\), and \(C=n-1\). Then \[\begin{split} A^3+B^3+C^3-3ABC&=2n^3+(n-1)^3-3n^2(n-1)\\ &=2n^3+n^3-3n^2+3n-1-3n^3+3n^2\\ &=3n-1 \end{split}\] Aha! So we can construct every positive integer congruent to 2 modulo 3. Likewise, we find that the expression yields \(3n-2\) when we set \(A=n\) and \(B=C=n-1\), so we can also construct every positive integer congruent to 1 modulo 3. Now we know that every positive integer that is not a multiple of 3 is in the range. How about multiples of 3? Strangely, I was not able to construct 3 or 6 with the triples that I tried, and it did not seem like higher triples would generate these numbers, as the repeat hits that I was getting occurred relatively quickly after the first triple I found that generated that particular number. I was, however, able to construct 9 and 18 with any permutations of the triples \((0,1,2)\) and \((1,2,3)\), respectively. This strongly suggested that I try out a permutation of \((n,n-1,n-2)\). Doing the algebra, I indeed found that the expression simplified to \(9(n-1)\). So now I know that I can construct any positive multiple of 9. At this point, I conjecture that I cannot construct a multiple of 3 that is not a multiple of 9. Another way to frame this is, if there is a multiple of 3 in the range, then it must also be a multiple of 9. If the expression was a multiple of 3, since obviously \(3ABC\equiv0\pmod{3}\), I required \(A^3+B^3+C^3\equiv0\pmod{3}\). I had also observed (a bit earlier if I remember correctly) that \(n^3\equiv n\pmod{3}\) in all three possible cases. So now, we simply required \(A+B+C\equiv0\pmod{3}\). There are precisely four cases where this occurs. Case 1: \((A,B,C)\equiv (0,0,0)\pmod{3}\) In this case, all three numbers have at least one factor of 3, so their cubes have at least three factors of 3. Furthermore, the product \(3ABC\) must have at least four factors of 3. Hence, we have in this case \[A^3+B^3+C^3-3ABC\equiv0\pmod{9}.\] Case 2: \((A,B,C)\equiv (1,1,1)\pmod{3}\) We can write \(A=3x+1\), \(B=3y+1\), and \(C=3z+1\) for \(x,y,z\in\mathbb{Z}\). Plugging these into the expression, we find that the expansion consists of coefficients that are all divisible by 9. Hence, once again we obtain \[A^3+B^3+C^3-3ABC\equiv0\pmod{9}.\] Case 3: \((A,B,C)\equiv (2,2,2)\pmod{3}\) Similar to the previous case, we bash out the expression, but setting \(A=3x+2\), \(B=3y+2\), and \(C=3z+2\) this time. Once again, the coefficients end up being divisible by 9. Hence in this case, \[A^3+B^3+C^3-3ABC\equiv0\pmod{9}.\] Case 4: \((A,B,C)\equiv \textrm{some permutation of }(0,1,2)\pmod{3}\) In this case, WLOG let the permutation of the ordered triple above be \((0,1,2)\). Then, by our arguments in the first case, both \(A^3\) and \(3ABC\) are divisible by 9. For the remaining terms, we have \[\begin{split} B^3+C^3&=(B+C)(B^2+C^2-BC)\\ &\equiv (1+2)(1+4-2)\pmod{3} \end{split}\] Observe that both factors are congruent to 0 modulo 3, so the sum \(B^3+C^3\) is also divisible by 9. Hence we have in this case \[A^3+B^3+C^3-3ABC\equiv0\pmod{9}.\] So we can see that we can construct 0 (duh), every positive integer that is not a multiple of 3, every positive integer that is a multiple of 9, and that whenever we construct a multiple of 3 it must also be a multiple of 9. So the range is all nonnegative integers except for multiples of 3 which are not multiples of 9. \(\square\) Phew! Problem (IMO 1959): Prove that for natural \(n\) the fraction \(\frac{21n+4}{14n+3}\) is irreducible.
Solution: Suppose to the contrary that the fraction is reducible. Then, there must exist a prime \(p|21n+4\) and \(p|14n+3\). In other words, \(21n+4\equiv0\pmod p\) and \(14n+3\equiv0\pmod p\). Adding these two congruences: \[7(5n+1)\equiv0\pmod p.\] Observe that \(p\neq7\), since \(7\) divides neither \(21n+4\) nor \(14n+3\). Hence: \[5n+1\equiv0\pmod p.\] Suppose \(p=2\). Then to satisfy this congruence, \(n\) must be odd. But then \(21n+4\) would be odd and \(p=2\) would not be able to divide it, contradiction. Hence \(p\neq2\) and it must instead be an odd prime. Subtracting the two original congruences yields: \[7n+1\equiv0\pmod p.\] Now subtracting this congruence with the previous one, we obtain \[2n\equiv0\pmod p.\] Since \(p\neq2\), we must have \[n\equiv0\pmod p.\] But now, \(21n+4\equiv4\pmod p\), and \(4\equiv 0\pmod p\) if and only if \(p=2\), contradiction. Hence there cannot be a prime that divides both \(21n+4\) and \(14n+3\) and the fraction \(\frac{21n+4}{14n+3}\) must be irreducible. \(\square\) Edit: Yes, I know the result immediately follows from the Euclidean algorithm. For some reason, I could only remember the extended Euclidean algorithm when I was solving this problem. Last Saturday, on my way to a Mu Alpha Theta competition, I had an interesting thought. I was thinking about how people could lie about their IQs by rounding them. Obviously, this is only really effective if your IQ increases upon rounding. For instance, it doesn't do any good to round an IQ of 132 to the nearest 10 because the result is actually less than 132. Then, I realized that you could round to different numbers. For instance, with an IQ of 133, instead of rounding to the nearest 10, one could round to the nearest 5 to obtain 135. Sillily, I wondered what would happen if someone tried to further obscure their true IQ by rounding already rounded values. For instance, rounding 132 to the nearest 1 yielded, 132. Then, rounding that to the nearest 2 again yielded 132. Rounding to the nearest 3, we again have 132. Rounding to the nearest 4, we have 132. But when we round to the nearest 5, we drop down to 130. Now, we take 130 and round it to the nearest 6. This brings us back up to 132. Next, we are up to 133. I quickly realized that this sequence was fascinating. It had a simple recursive definition: \(a_n\) was obtained by rounding \(a_{n-1}\) to the nearest \(n\). I wrote a program to generate these sequences and what I found was quite shocking. Every single sequence seemed to converge to an arithmetic sequence after a certain number of terms. Let \(a_k\) be the particular term when the sequence enters an arithmetic sequence. Results from my program seemed to imply that \(a_k=\frac{k^2}{2}\) for even \(k\) (this was actually an observation from William He). We did not explicitly find \(a_k\) for odd \(k\) initially. It wasn't until I took the marker to the whiteboard when more progress was made. Observe that \(a_n=np\) for \(p\in\mathbb{Z}\). Hence, consecutive terms were given by \(np\) and \((n+1)q\) for \(p,q\in\mathbb{Z}\). For all \(a_n\), there exists a set of possible \(q\), which I will call \(Q\). I was able to prove that if \(p=\max{Q}\), then \(q=p\). When \(q=p\), the sequence (obviously) becomes arithmetic. Furthermore, if this occurred, I was able to show that \(a_k=\frac{k^2}{2}\) for even \(k\) and that \(a_k=\frac{k(k+1)}{2}\) for odd \(k\). Running my program a couple of times, it seemed that for odd \(k\), the equation \(a_k=\frac{k(k+1)}{2}\) was actually true! The problem is that I have not proven that \(p\) ever actually equals \(\max{Q}\). This is the final missing piece. I am confident, however, that I am correct, especially since my program is confirming my explicit formulas for \(a_k\). The graphs of the sequence are even more beautiful. I graphed the sequence for starting terms of 500, 1000, and 2000, focusing on the behavior of the sequence before it converged to an arithmetic sequence. The number of bounces clearly increases as the first term increases. Also, the bounces appear to approach a parabolic shape as the first term is increased. These may be new avenues of investigation after I can prove that the sequence always converges to an arithmetic sequence.
But for now, I'll keep looking for that missing piece. |
Categories
All
Archives
July 2023
|