My life was so busy for the past two days I didn't even have time to post things on here. Luckily, Thanksgiving break has started so I have plenty of time to learn things. Currently, I'm reading a number theory book that I randomly picked out at my library, it's by Nagell. It turns out that this book has a lot of good exercises and I've decided to post some of the interesting ones on here. The following ones come from the chapter on congruences.
53. Let $f(x)$ be an integral polynomial in $x$, and let $n,m$ be natural numbers. Show that there exists an integer $x_0$ such that each of the numbers \[ f(x_0),f(x_0+1),...,f(x_0+n-1)\] has at least $m$ different prime divisors.
Lemma: For an integer polynomial non-constant $f(x)$, show that there is an infinite number of primes $p$ that can divide $f(x)$.
Proof: Assume the contrary that there's only a finite number of primes denoted by $p_1,p_2,...,p_k$ that can divide $f(x)$. Let $e_i$ denote the number satisfying $p^{e_i-1}||f(0)$, then $p^{e_i-1}||f(mp^{e_i})$ for $m\in \mathbb {Z}$. Consider the number function $g(n)=n\prod_{i=1}^{k}p^{e_i}$ where $n\in \mathbb {Z}$, thus $\prod_{i=1}^{k}p^{e_i-1}||f(g(n))$. Since there clearly exists $n$ such that $f(g(n))>\prod_{i=1}^{k}p^{e_i-1}$, this must mean that there exists a prime not one of $p_1,p_2,...,p_k$ dividing $f(g(n))$, which contradicts our original assumption.
Main Proof: By the Lemma above, one can select $n$ groups of $m$ primes that can divide $f(x)$: $S_1,S_2,...,S_n$ such that $S_i\cap S_j=\emptyset$ for $1\le i<j\le n$. By Chinese remainder theorem, there exist $r_i$ such that $\prod_{p\in S_i}p|f(r_i)$. In addition by Bezout's Lemma, one can find $n$ consecutive integers $x_0,x_0+1,...,x_0+n-1$ such that $x_0+i-1\equiv r_i \pmod {\prod_{p\in S_i}}$ for $i=1,2,...,n$. Hence $\prod_{p\in S_i}|f(x_0+i-1)$ which means each $f(x_0+i-1)$ is divisible by $m$. $\Box$.
Friday, November 21, 2014
Tuesday, November 18, 2014
Rusty
Today I went to math club and it made me realize how rusty I am at AMC problems. Then again, I had been having trouble thinking all day. I tried to understand what my teacher said about this one problem but I just couldn't concentrate. If I were to make an impression of myself today, I would have done a really bad job.
Problem: Find all positive integers $n$ and $p$ if $p$ is prime and \[ n^8 - p^5 = n^2+p^2 . \]
Solution:
We first manipulate the equation to get \[ n^2(n^3+1)(n^3-1)=p^2(p^3+1) \]. Clearly there's no solution for $p=2$, assume from now that $p$ is odd. Note that the factors on the left cannot pair-wisely share any factors larger than $2$, therefore $p^2$ divide exactly one of the factors, which leads to the following three cases:
Case 1: $p^2|n^2$ or $p|n\Rightarrow n=pk$ for $k\in \mathbb {N}$. However since $p^3+1\ge n^3+1$, therefore $k=1\Rightarrow n^3-1=1\Rightarrow $no solution.
Case2: $p^2|n^3-1$, let $n^3-1=p^2k$ for $k\in \mathbb {N}$. We have \[n^2k(p^2k+2)=p^3+1\], this means $p^2k+2|p^3+1\Rightarrow p^2k+2|2p-k$. Since $k<p$, therefore $2p-k\ge p^2k+2\ge p^2+2\Rightarrow 2p-1\ge p^2+2 \Rightarrow$ no solution
Case3: $p^2|n^3+1$, let $n^3+1=p^2k$ for $k\in \mathbb {N}$. We have \[n^2k(p^2k-2)=p^3+1\], this means $k<p+1,p^2k-2|p^3+1\Rightarrow p^2k-2|2p+k\Rightarrow 2p+k\ge p^2k-2$ $\ge p^2-2\Rightarrow 3p+1>p^2-2\Rightarrow p=2,3$ which gives the solution $(p,n)=(3,2)$
In conclusion after covering all possible cases, $(p,n)=(3,2)$ is the only solution. $\Box$
Note to solution: In non-rigorous terms, I feel like the key to this solution is comparing sizes.
Next Challenges(I've decided to add a few more to improve my other areas, also these problem are all from the 2004 shortlist):
1.Let $k$ be a fixed integer greater than 1, and let ${m=4k^2-5}$. Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$ defined by
$ x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,$
has all of its terms relatively prime to $m$.
2. Let $p$ be an odd prime and $n$ a positive integer. In the coordinate plane, eight distinct points with integer coordinates lie on a circle with diameter of length $p^{n}$. Prove that there exists a triangle with vertices at three of the given points such that the squares of its side lengths are integers divisible by $p^{n+1}$
3. Given a cyclic quadrilateral $ABCD$, let $M$ be the midpoint of the side $CD$, and let $N$ be a point on the circumcircle of triangle $ABM$. Assume that the point $N$ is different from the point $M$ and satisfies $\frac{AN}{BN}=\frac{AM}{BM}$. Prove that the points $E$, $F$, $N$ are collinear, where $E=AC\cap BD$ and $F=BC\cap DA$
Problem: Find all positive integers $n$ and $p$ if $p$ is prime and \[ n^8 - p^5 = n^2+p^2 . \]
Solution:
We first manipulate the equation to get \[ n^2(n^3+1)(n^3-1)=p^2(p^3+1) \]. Clearly there's no solution for $p=2$, assume from now that $p$ is odd. Note that the factors on the left cannot pair-wisely share any factors larger than $2$, therefore $p^2$ divide exactly one of the factors, which leads to the following three cases:
Case 1: $p^2|n^2$ or $p|n\Rightarrow n=pk$ for $k\in \mathbb {N}$. However since $p^3+1\ge n^3+1$, therefore $k=1\Rightarrow n^3-1=1\Rightarrow $no solution.
Case2: $p^2|n^3-1$, let $n^3-1=p^2k$ for $k\in \mathbb {N}$. We have \[n^2k(p^2k+2)=p^3+1\], this means $p^2k+2|p^3+1\Rightarrow p^2k+2|2p-k$. Since $k<p$, therefore $2p-k\ge p^2k+2\ge p^2+2\Rightarrow 2p-1\ge p^2+2 \Rightarrow$ no solution
Case3: $p^2|n^3+1$, let $n^3+1=p^2k$ for $k\in \mathbb {N}$. We have \[n^2k(p^2k-2)=p^3+1\], this means $k<p+1,p^2k-2|p^3+1\Rightarrow p^2k-2|2p+k\Rightarrow 2p+k\ge p^2k-2$ $\ge p^2-2\Rightarrow 3p+1>p^2-2\Rightarrow p=2,3$ which gives the solution $(p,n)=(3,2)$
In conclusion after covering all possible cases, $(p,n)=(3,2)$ is the only solution. $\Box$
Note to solution: In non-rigorous terms, I feel like the key to this solution is comparing sizes.
Next Challenges(I've decided to add a few more to improve my other areas, also these problem are all from the 2004 shortlist):
1.Let $k$ be a fixed integer greater than 1, and let ${m=4k^2-5}$. Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$ defined by
$ x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,$
has all of its terms relatively prime to $m$.
2. Let $p$ be an odd prime and $n$ a positive integer. In the coordinate plane, eight distinct points with integer coordinates lie on a circle with diameter of length $p^{n}$. Prove that there exists a triangle with vertices at three of the given points such that the squares of its side lengths are integers divisible by $p^{n+1}$
3. Given a cyclic quadrilateral $ABCD$, let $M$ be the midpoint of the side $CD$, and let $N$ be a point on the circumcircle of triangle $ABM$. Assume that the point $N$ is different from the point $M$ and satisfies $\frac{AN}{BN}=\frac{AM}{BM}$. Prove that the points $E$, $F$, $N$ are collinear, where $E=AC\cap BD$ and $F=BC\cap DA$
Monday, November 17, 2014
Solution to Problem in the First Post
Well, I thought it would've taken longer for me to solve the problem but after more effort on observation I succeeded. Here goes the solution:
Problem: Let \(p\) be a prime, prove that \(7p+3^p-4\) cannot be a perfect square
Solution:
When \(p=2, 7*2+3^2-4=19\) is not a perfect square.
When $p$ is an odd prime, suppose there exists $p$ such that $7p+3^p-4$ is perfect equare. Since $7p+3^p-4=n^2$ is even, therefore $7p+3^p-4\equiv 7p-1\equiv 0\pmod 4\Rightarrow p\equiv 3\pmod 4$. Next, note that $n^2+1\equiv 7p+3^p-3\equiv 0\pmod p$ by Fermat's Little theorem. However, it's well known that numbers of the form $n^2+1$ only have prime divisors$\equiv 1\pmod 4$, thus we've reached a contradiction and established \(7p+3^p-4\) cannot be a perfect square. $\Box$
Note to Solution: Before finding this solution, I tried examining different modules, especially $\pmod 6$ with high hopes because it has proven to be effective on problems with primes.
Next Challenge: Find all positive integers $n$ and $p$ if $p$ is prime and \[ n^8 - p^5 = n^2+p^2 . \]
Problem: Let \(p\) be a prime, prove that \(7p+3^p-4\) cannot be a perfect square
Solution:
When \(p=2, 7*2+3^2-4=19\) is not a perfect square.
When $p$ is an odd prime, suppose there exists $p$ such that $7p+3^p-4$ is perfect equare. Since $7p+3^p-4=n^2$ is even, therefore $7p+3^p-4\equiv 7p-1\equiv 0\pmod 4\Rightarrow p\equiv 3\pmod 4$. Next, note that $n^2+1\equiv 7p+3^p-3\equiv 0\pmod p$ by Fermat's Little theorem. However, it's well known that numbers of the form $n^2+1$ only have prime divisors$\equiv 1\pmod 4$, thus we've reached a contradiction and established \(7p+3^p-4\) cannot be a perfect square. $\Box$
Note to Solution: Before finding this solution, I tried examining different modules, especially $\pmod 6$ with high hopes because it has proven to be effective on problems with primes.
Next Challenge: Find all positive integers $n$ and $p$ if $p$ is prime and \[ n^8 - p^5 = n^2+p^2 . \]
Goals
It's already my junior year in high school; as my English teacher had said, you are less than two years away from "real" life. To be honest with you, being in the middle of a conundrum, I'm not ready at all. What college will I be going to? What is my futrue job gonna be? Can I even survive with my current abilities? Attempts will be made to answer these question throughout this blog jouney. Although I have a pretty evident persistent issue, starting today, I will write at least one post up in here to keep myself going. It could be about math, physics, my school adventure, or other topics that I want to talk about. Without further ado, let's start off by challenging my self with the following problem, a problem that I couldn't solve in 15 minutes:
Let \(p\) be a prime, prove that \(7p+3^p-4\) cannot be a perfect square.
Let's hope I can solve this one by tomorrow
Let \(p\) be a prime, prove that \(7p+3^p-4\) cannot be a perfect square.
Let's hope I can solve this one by tomorrow
Subscribe to:
Comments (Atom)