1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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


    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


    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