Online Course Discussion Forum

MCIII Number Theory 5.20, 5.23, 5.27, and 5.28

 
 
Picture of Tina Jin
MCIII Number Theory 5.20, 5.23, 5.27, and 5.28
by Tina Jin - Friday, 5 January 2024, 8:44 PM
 

Hello!

5.20: A little bit stuck, here's what I tried to do:

n^2+5n+16-169k=0 then fixing values for k and then I tried fixing values for n.

I also tried factoring: (n+4)^2-3n=169k

5.23: I tried some factoring like (n-1)(n+1)(n^2+1)(n^4+1)<1 which means n=1 right? 

5.27: I got (x-2)(x-5)(x-5)(x-5)=4 works, so x=a+4=b+1=c+1=d+1. But that's not correct, why though?

5.28: Here is what I did:


So that means n=1 (since -x corresponds to -x^n) or -x^n corresponds to something else, namely -x^(nm+1) then -x^(m+1) would correspond to -x since exponents cannot change the sign of the expression, as in no integers k exist such that x^k=-x^k for all x. Then m=0 but m has to be positive.

So that means n must equal to 1 and plugging in n=1 gives m=any positive integer.

What did I do wrong?

Thank you,

Tina Jin

 
Picture of Tina Jin
Re: MCIII Number Theory 5.20, 5.23, 5.27, and 5.28
by Tina Jin - Friday, 5 January 2024, 8:46 PM
 
I just realized the image did not show up, here it is again:


Picture of Dr. Kevin Wang
Re: MCIII Number Theory 5.20, 5.23, 5.27, and 5.28
by Dr. Kevin Wang - Monday, 29 January 2024, 11:35 PM
 

The first fraction is not correct.  The numerator should be $x^{n(m+1)}$ instead of $x^{nm+1}$.  There is a big difference.

This problem is question number 1 in USAMO 1977.  The solution:

Let \[ P(x) = \frac{1+x^n+x^{2n}+\cdots+ x^{mn}}{1+x+x^2 + \cdots + x^m} = \frac{(x^{(m+1)n}-1)(x-1)}{(x^n-1)(x^{m+1}-1)}. \] For all positive integers $m$ and $n$, $x^n-1$ and $x^{m+1}-1$ are both factors of $x^{(m+1)n}-1$. So as long as $x^n-1$ and $x^{m+1}-1$ do not have common factor (or common roots of unity) other than $x-1$, $P(x)$ is a polynomial with integer coefficients. On the other hand, if $x^n-1$ and $x^{m+1}-1$ have a common factor other than $x-1$, it means the equations $x^n-1=0$ and $x^{m+1}-1=0$ have common roots other than $x=1$, but the equation $x^{(m+1)n}-1=0$ has no repeated roots, so in this case $P(x)$ is not a polynomial.\\ Therefore the polynomials $x^n-1$ and $x^{m+1}-1$ do not have any common factor besides $x-1$, in other words, $\gcd(m+1, n)=1$.

Picture of Dr. Kevin Wang
Re: MCIII Number Theory 5.20, 5.23, 5.27, and 5.28
by Dr. Kevin Wang - Saturday, 6 January 2024, 12:47 AM
 

5.20: Since $169=13^2$, you can try to analyze in mod 13 first.

5.23: This doesn't look like the correct question.  What is the actual question?

5.27: How do you write $4$ as a product of four distinct integers?

5.28: Be very careful to read the question.  Especially the numerator polynomial.

Picture of Tina Jin
Re: MCIII Number Theory 5.20, 5.23, 5.27, and 5.28
by Tina Jin - Sunday, 14 January 2024, 1:05 PM
 

I still need some help/hints on these problems.

5.20: I tried analyzing in mod 13, I tried adding and subtracting numbers to make it factorable, but then I guessed and checked a little bit and got some solutions for congruent to 0 mod 13, and I'm not sure how many solutions are congruent to 0 mod 169. 

5.21: I believe that is the right question about the function f(n) < or >n. Here is my work:


5.27: (-1)(1)(2)(-2) so the answer should be x=a-1=b+1=c+2=d-2, which is still not correct. Why?

5.28: The numerator polynomial should be (x^(nm+n)-1)/(x^n-1), but that gives the conclusion that n=1 and m can be any integer. Why is the answer then?

Thanks!

Tina Jin

Picture of Dr. Kevin Wang
Re: MCIII Number Theory 5.20, 5.23, 5.27, and 5.28
by Dr. Kevin Wang - Wednesday, 24 January 2024, 12:19 AM
 

Let me explain 5.27 first.  The question asks to express $x$ in terms of $a,b,c,d$.  Probably your result $x=a-1=b+1=c+2=d-2$ is acceptable.  The intended answer is $x=(a+b+c+d)/4$.

Picture of Dr. Kevin Wang
Re: MCIII Number Theory 5.20, 5.23, 5.27, and 5.28
by Dr. Kevin Wang - Thursday, 25 January 2024, 4:09 PM
 

5.20: Analyze mod 13 first.  Testing $n^2+5n+16$ for $n=0,1,2,3,\ldots,12$, we can see that only $n\equiv 4\pmod{13}$ can make $n^2+5n+16$ a multiple of $13$. (Alternatively, to avoid testing out the numbers $0,1,2,3,\ldots,12$ by brute force, you can rearrange the terms to get $n^2+5n+16 = (n-4)^2 + 13n$, and this means $n\equiv 4\pmod{13}$.)

Since $n-4$ is a multiple of $13$, we plug in $n=13k+4$, and then $n^2+5n+16 = 169k^2 + 169k + 36$, and this is not a multiple of $169$.  Therefore, there is no solution.

Picture of Dr. Kevin Wang
Re: MCIII Number Theory 5.20, 5.23, 5.27, and 5.28
by Dr. Kevin Wang - Monday, 29 January 2024, 11:20 PM
 

5.23: The question defines a function $f(n)$ to be the last 4 digits of $n^9$, for $n < 10000$. Then compare an odd number $n$ and $f(n)$ (note that both are odd).  The question is: for odd numbers below $10000$, which occurs more: $n > f(n)$ (this is set $A$), or $n < f(n)$ (this is set $B$)?  First we may consider, are there cases where $f(n)=n$?  Obviously $n=1$ is one of the equality cases.  Are there more?  If you think carefully, $n=9999$ is another, because $9999\equiv -1\pmod{10000}$, and $(-1)^9\equiv -1\pmod{10000}$.  Those values correspond to the factors $n-1$ and $n+1$ in the factorization of $n^9-n$.  Are there more?  From the factorization, it doesn't look like there are more equality cases.  However, those two values add up to $10000$, and perhaps we can also look at the other numbers in pairs.

So for odd number $a$, consider $b = 10000-a$.  Then $a+b=10000$.  We also know that $a^9 + b^9$ has a factor $a+b$.  Since $a+b=10000$, we have $10000 \mid a^9+b^9$.  That means, $f(a) + f(b) \equiv 0\pmod{10000}$.  But we can also see that $f(a)+f(b)$ is not $0$, so it must be that $f(a)+f(b) = 10000$.

Based on the above analysis, if $a > f(a)$, then $b < f(b)$.  Therefore, the numbers in $A$ and $B$ are actually matched up, and that means these two sets have the same number of elements.