Master Number Theory Questions Easily | Proving Formulas & Theorems"

In summary, the conversation involves discussing three different problems involving positive integers and their properties, including proving the formula for phi(n) and using Euler's and Wilson's theorems. The participants share their approaches and provide hints and suggestions to help each other solve the problems. Eventually, all three problems are successfully solved.
  • #1
randommacuser
24
0
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.
 
Physics news on Phys.org
  • #2
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.
 
  • #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?
 
  • #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.
 
  • #5
first one...u should know phi(n), now treat mn as single integer "mn" ...what is phi("mn");
 
  • #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.
 
  • #7
randommacuser said:
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.

randommacuser said:
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...
 
  • #8
Got them all, I think. Thanks everyone!
 
  • #9
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!
 

What is master number theory?

Master number theory is a branch of mathematics that deals with the properties and relationships of numbers, particularly integers. It involves studying patterns and structures within numbers and using them to solve problems and prove theorems.

Why is it important to study master number theory?

Master number theory is important because it helps us understand the fundamental principles of mathematics and provides a foundation for many other fields of study such as cryptography, computer science, and physics. It also has practical applications in everyday life, such as in banking and coding.

What are some common formulas and theorems used in master number theory?

Some common formulas and theorems used in master number theory include the Euclidean algorithm, the Chinese remainder theorem, and Fermat's little theorem. These are used to solve problems involving divisibility, modular arithmetic, and prime numbers.

How can one easily prove formulas and theorems in master number theory?

To prove formulas and theorems in master number theory, one must have a solid understanding of the concepts and properties involved. It also helps to practice by solving a variety of problems and familiarizing oneself with different proof techniques, such as induction, contradiction, and direct proof.

What are some practical ways to apply master number theory?

Master number theory has many practical applications, such as in coding and cryptography. It is used to create secure algorithms for data encryption and decryption. It is also used in banking for tasks such as credit card authentication and fraud detection. Additionally, master number theory is used in computer science for tasks such as data compression and error correction.

Similar threads

Replies
18
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
439
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
434
  • Calculus and Beyond Homework Help
Replies
1
Views
522
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
743
  • Calculus and Beyond Homework Help
Replies
3
Views
482
Back
Top