## Number theory questions

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.

 PhysOrg.com science news on PhysOrg.com >> Front-row seats to climate change>> Attacking MRSA with metals from antibacterial clays>> New formula invented for microscope viewing, substitutes for federally controlled drug
 Recognitions: Gold Member Science Advisor Staff Emeritus 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.
 Recognitions: Gold Member Science Advisor Staff Emeritus 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.

## Number theory questions

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.

 Recognitions: Gold Member 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 begining 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 begining 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.
 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
 Recognitions: Homework Help Science Advisor 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.
 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/interestingl...orization.html
 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