Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theory questions

  1. Jul 17, 2004 #1
    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.
     
  2. jcsd
  3. Jul 17, 2004 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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

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

    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.
     
  4. Jul 17, 2004 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  5. Jul 18, 2004 #4
    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.
     
    Last edited: Jul 18, 2004
  6. Jul 18, 2004 #5
    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.
     
  7. Aug 2, 2004 #6
    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
     
  8. Aug 2, 2004 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  9. Aug 3, 2004 #8
  10. Aug 3, 2004 #9
    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 :approve:

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number theory questions
  1. Number Theory Question (Replies: 9)

Loading...