What are Some Challenging Number Theory Problems?

[ukamle]

Questions:


1) How many zeros are there at the end of 1994!
[where n ! stands for n factorial]

2) Prove that if x1, x2, ..., x100 are distinct natural odd numbers
1/x1 + 1/x2 + ... + 1/x100 < 2

3) Prove that if 'p' is a prime number then coefficients of the terms of (1+x)^(p-1) are alternately greater and less by unity than some multiples of 'p'.

4) Prove that 2222^5555 + 5555^2222 is divisible by 7.

 

[Gokul43201]

1) How many 2's in the prime factorization of 1994 ! and how many 5's ? See how these are respectively equal to

$$\sum_{i>0} [\frac {1994} {2^i}] ~~and~~ \sum_{i>0} [\frac {1994} {5^i}]$$

where [ ] is the greatest integer (or floor) function. ex : [5.31] = [5.99] = 5
The smaller of the above two sums gives you the number of zeros.

 

[Gokul43201]

2) Clearly the largest value of this sum is 1 + 1/3 + 1/5 + 1/7 +... 1/199. This sum is greater than 2 (I think it exceeds 2 at the 8th or 9th term). So unless 1 is disallowed, this question is wrong.

 

[Wong]

4) This answer is from some "brute force" caculation:
2222 (mod7) = 3
2222^2 (mod7) = 3^2 (mod7) = 2
2222^3 (mod7) = 3^3 (mod7) = 6
...
We find a pattern 3, 2, 6, 4, 5, 1, 3, 2, 6, 4, 5, 1 ...for increasing powers of 2222. Do the same for 5555. The pattern is 4, 2, 1, 4, 2, 1...

Now 5555 (mod6) = 5, so 2222^5555 (mod7) = 5. 2222 (mod3) = 2, so 5555^2222 (mod7) = 2. From this the result follows.

 

[robert Ihnot]

3) Prove that if 'p' is a prime number then coefficients of the terms of (1+x)^(p-1) are alternately greater and less by unity than some multiples of 'p'.

We look at the Pascal Triangle: 1/1,1/1,2,1/1,3,3,1/1,4,6,4,1...(This is sort of hard to write out but by "/" I mean to place it underneath on the next line.) The Pacal Triangle is a way of obtaining the coefficients in the binominal expansion moving from N to N+1.

In general if we have the line 1,A,B,C,...The line under it will be written beginning with 1 and then adding the numbers on both sides from above. This gives a new line: 1, 1+A, A+B, B+C, C+D,...1. If this last line is divisible by p everywhere except for the beginning and ending 1s, we have 1+A==0 Mod p or A==-1, then the next case is A+B==0 Mod n, thus, B==-A==1, so that the coefficients alternate modulo p as we move along the line.

 

[ukamle]

1) First solution submitted by gokul43201 is correct and is a direct consequence of prime factorization theorem.



2) I m sorry I forgot to mention that the number is not divisible by primes greater than certain prime say 5.
According to factorization theorem
every number can be represented as 2^a * 3^b * 5^c *...

since the number is odd there is no power of 2 in the expression
since the number is not divisible by any prime > 5
therefore the number can be represented as 3^x * 5^y
each x1, x2,...x100 is of the form of 3^x * 5^y
Consider the series
(1/3^0 + 1/3^1 + 1/3^2 + ... infinity) * (1/5^0 + 1/5^1 + ... infinity)

this product will contain all the possible pairs of 3^x * 3^y.
Therefore the sum 1/x1 + 1/x2 + ... + 1/x100 should be less than this product
This product after solving equals 2
Hence the sum is less than 2.


3) The solution given by Robert Ihnot is very elegant since it involves Pascal's triangle.

My proof uses the same binomial coefficients
Proof:

(1+x)^(p-1) = (p-1)C0 * x^n + (p-1)C1 * x^(n-1) + ... + (p-1)Cr * x^(n-r) ... (p-1)C(p-1)

where nCr represents n ! /r ! * (n-r)!

Now,
constant term in (p-1)*(p-2)*(p-3)*...(p-r) = (-1)^r * r!
Therefore, (p-1)*(p-2)*...(p-r)/ r! = [p^r + A* p^(r-1) +... ]/r! + (-1)^r

First term is a multiple of p
Second term is (-1)^r

Hence the required condition has been proved


4) The solution is nice as submitted by Wong.
Though an alternate solution can be done without using brute force.

Well if you observe carefully

2222 is in the form of 7m + 3 and 5555 is in the form of 7t +4

2222 ^ 5555 + 5555 ^ 2222 can be written as

(2222^5555 + 4^5555) + (5555 ^ 2222 - 4^2222) +(4^2222 -4^5555)

Checking all terms for divisiblity tests it can be shown that the expression is divisible by 7.

Question:
Prove that the expression
f(x) = An * x^n + A(n-1) * x^(n-1) +... + A1 *x + A0 is composite for some integer x.

A1, A2, ... An are con

 

[matt grime]

consider the values f(rA0) for lots of different r, they are all divisible by all the factors of A0, they can't all be (the same) prime or zero for all r.

 

[maverick280857]

Hi Unmesh...

Gokul's solution uses the popular "exponent of prime" relationship which you can easily encounter in any elementary text on number theory (with a proof, such as in Zuckermann..which I would highly recommend if you're interested in number theory :-))...

EDIT: You might be interested in this: http://www.mathmojo.com/interestinglessons/primefactors/primefactorization.html

 

[maverick280857]

Well I looked at the number theory (useful concept problem sheet) problem set where you got these problems from and I discovered how crucial 5 is to problem 2

To add to my previous post...you might want to check out Kummer's Theorem's consequence about E[p] (exponent of prime).

Cheers
Vivek