Online Course Discussion Forum

How to do MCIII 5.33 Number Theory?

 
 
Picture of Ethan Song
How to do MCIII 5.33 Number Theory?
by Ethan Song - Monday, 18 May 2020, 5:21 PM
 
The Problem is: Do there exist 100 distinct positive integers, such that the product of any 5 is divisible by the sum of those 5?


As long as there is a zero, then it is divisible, by they are distinct positive integers. So how would I approach this problem?

 
Picture of Dr. Kevin Wang
Re: How to do MCIII 5.33 Number Theory?
by Dr. Kevin Wang - Tuesday, 19 May 2020, 12:04 AM
 

This is solved by construction.  Let me give you a hint to begin with: can you find $5$ positive integers $a$, $b$, $c$, $d$, $e$, such that $abcde$ is divisible by $a+b+c+d+e$?  Further hint: based on any randomly selected $5$ positive integers $a$, $b$, $c$, $d$, $e$, can you multiply them by the same number to get $5$ new numbers such that the product of the new numbers is divisible by their sum?

Once you work out the case for $5$ numbers, you can try to construct $100$ numbers to satisfy the requirement (or any $N$ numbers where $N\geq 5$).

Picture of Ethan Song
Re: How to do MCIII 5.33 Number Theory?
by Ethan Song - Tuesday, 19 May 2020, 12:52 PM
 

For the first hint, I believe just 1,2,3,4,5 works, since 120 is divisible by 15.

On any 5 random positive integers, you can multiply then by any >0 integer and still get (a+b+c+d+e) | abcde right? 

So I can multiply by 6 to get 6,12,18,24,30 and then so on. How do i make sure any 5 of these will work??


Picture of Dr. Kevin Wang
Re: How to do MCIII 5.33 Number Theory?
by Dr. Kevin Wang - Tuesday, 19 May 2020, 4:15 PM
 

For any randomly selected numbers (not necessarily satisfying the requirement yet), what number $k$ can you use to multiply by each of them to get $5$ new numbers that satisfy the requirement?  This number $k$ is important and cannot be any number, because the starting $5$ numbers might not have $(a+b+c+d+e) | abcde$.

Picture of Ethan Song
Re: How to do MCIII 5.33 Number Theory?
by Ethan Song - Thursday, 21 May 2020, 2:12 PM
 

Hi Dr.Wang, I found out that we want (k^4*abcde)/(a+b+c+d+e) to be an integer, so as long as k^4 is a multiple of a+b+c+d+e, we are good. However, I'm not sure how this helps. You can derive 5 working numbers from any 5 numbers, but how would we find 100?

Picture of Dr. Kevin Wang
Re: How to do MCIII 5.33 Number Theory?
by Dr. Kevin Wang - Thursday, 21 May 2020, 3:34 PM
 

That's a very good result.  Let's simplify it: for any randomly selected positive integers $a$, $b$, $c$, $d$, $e$,  as long as $k$ is a multiple of $a+b+c+d+e$, then $ka$, $kb$, $kc$, $kd$, $ke$ satisfy the requirement (product is divisible by sum).

Now for the case of $100$ numbers, we can select $100$ arbitrary numbers to begin with, then there are $\displaystyle\binom{100}{5}$ groups of $5$ numbers, each has a sum.  Let $k$ be the least common multiple of these sums, then multiply all these $100$ numbers by $k$, and we get the set of numbers that satisfy the requirement.

Picture of Ethan Song
Re: How to do MCIII 5.33 Number Theory?
by Ethan Song - Friday, 22 May 2020, 11:18 PM
 
That solution is nice :) Could I also get some help on 5.32? 


The Problem : Find the minimum positive integer m such that $2^{1990} | (1989^{m}-1)$

I tried to write it as an equation, $k*2^{1990}=1989^{m}-1,$ and took it mod 1989. However 1989 isn't prime, and also i got $\phi(1989)=1152$ which doesn't really cut down the equation. Where can I proceed from here?

thank you!

Picture of Dr. Kevin Wang
Re: How to do MCIII 5.33 Number Theory?
by Dr. Kevin Wang - Monday, 25 May 2020, 11:38 PM
 

Write $m=2^t\cdot n$, where $n$ is an odd number.  Then use the factoring formula $$a^n - 1=(a-1)(a^{n-1}+a^{n-2}+\cdots+a+1),$$ and check the power of $2$ in each factor.

Picture of Ethan Song
Re: How to do MCIII 5.33 Number Theory?
by Ethan Song - Monday, 1 June 2020, 7:55 PM
 

Hi Dr. Wang, How would i easily find the amount of twos in the second part (1989^(2t*n-1+2^t*n-2+1989+1). Can i factore it out somehow?

Picture of Dr. Kevin Wang
Re: How to do MCIII 5.33 Number Theory?
by Dr. Kevin Wang - Tuesday, 2 June 2020, 3:31 PM
 

I don't think you got the second factor right.  Let $a=1989^{2^t}$, then the first factor is $a-1 = 1989^{2^t}-1$, and the second factor is:

$$a^{n-1} + a^{n-2} + \cdots + a + 1 = 1989^{2^t(n-1)} + 1989^{2^t(n-2)} + \cdots + 1989^{2^t} + 1.$$

When $n$ is an odd number, how many factor of $2$ do you think the second factor has?