Master Number Theory Questions Easily | Proving Formulas & Theorems"

[randommacuser]

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.

 

[shmoe]

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.

 

[devious_]

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?

 

[devious_]

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.

 

[neurocomp2003]

first one...u should know phi(n), now treat mn as single integer "mn" ...what is phi("mn");

 

[randommacuser]

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.

 

[shmoe]

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?

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.

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 ?

You'd then know gcd(n,9)=1, so...

 

[randommacuser]

Got them all, I think. Thanks everyone!

 

[Hurkyl]

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

\varphi(n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2}) \cdots

which makes your problem (1) trivial!