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

Homework Help: Number theory questions

  1. Mar 22, 2006 #1
    Hey all, I've got a few problems that are tripping me up tonight.

    1. Let m,n be positive integers with m|n. Prove phi(mn)=m*phi(n).

    I know I can write n as a multiple of m, and m as a product of primes, and my best guess so far is that I can work with some basic properties of or formulas for the phi function to get the desired result. But I'm not making much progress.

    2. Let n be an integer with 9|n. Prove n^7 = n mod 63.

    In this case I know it is enough to prove 7|(n^7-n) and 9|(n^7-n). But even though I imagine this would be a pretty simple application of Euler's theorem, I can't figure it out so far.

    3. Suppose p is prime and p = 3 mod 4. Prove ((p-1)/2)! = +/- 1 mod p.

    This one has me stumpted totally.
     
  2. jcsd
  3. Mar 22, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    1. can you prove the simpler case where n is a prime power? Your approach should be easier here.

    2. 9|(n^7-n) should be simple...Euler's theorem on 7|(n^7-n) is a good idea, what's going wrong? Show your work...

    3. A small hint, consider Wilson's theorem.
     
  4. Mar 22, 2006 #3
    1. Maybe you should think of a counting argument. What does m|n really tell you, and how can you count numbers coprime to mn in { 1, ..., m, ..., n, ..., mn }?

    2. n^7 = n (mod 7) by Fermat's Little Theorem (or Euler's Theorem), and you know that 9|n so 9|n^7. Can you see why n^7 = n (mod 9) too?

    3. Maybe Wilson's theorem will help. If you write p=4k+3 then
    (p-1)! = (4k+2)! = -1 (mod p)
    But also
    (4k+3)! = [(4k+2)(4k+1)...(2k+2)](2k+1)!
    = [(-1)(-2)(-3)...(-(2k+1))](2k+1)! (mod p)
    = - [(2k+1)!]^2 (mod p)
    and the minus sign is there because there are an odd number of terms (in fact we have (-1)^(2k+1) = -1).

    Can you see where to go from here?
     
  5. Mar 22, 2006 #4
    Oops. Looks like I'm half an hour too late. In my defense I didn't click the "Post" button properly then went to make dinner only to come back and see that it didn't actually post.
     
  6. Mar 22, 2006 #5
    first one...u should know phi(n), now treat mn as single integer "mn" ...what is phi("mn");
     
  7. Mar 22, 2006 #6
    I like this last suggestion for #1. I can do all that and I see where it is headed, but at the end I have expressions for phi(n) and phi(mn) that depend on different primes (or at least I can't prove they are the same). How do I use m|n to prove this?

    As I suspected, #2 is a lot easier than I was making it. I have a bit of a related question, though. If 3 does not divide n, how can I prove that n^7=n mod 9 ?

    Haven't had a chance to look at #3 yet, but I will.
     
  8. Mar 22, 2006 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    The primes involved in the factorizations of n and m*n have to be the same as m|n, they will possibly be different powers though.

    You'd then know gcd(n,9)=1, so...
     
  9. Mar 22, 2006 #8
    Got them all, I think. Thanks everyone!
     
  10. Mar 23, 2006 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    A useful form of the formula for phi(n) that I don't see often is:

    [tex]\varphi(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots[/tex]

    which makes your problem (1) trivial!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook