Proving Euler's Phi Function: Any Help Appreciated!

[kingwinner]

"Let m and k be positive integers and φ(m) is the Euler's phi function. Then the number of integers n such that 1≤n≤mk and (n,m)=1 is kφ(m)."


I can't figure out why this is true. How can we prove it?

Can someone explain this, please?
Any help is appreciated!

 

[dodo]

Coprimes repeat in a kind of "modular" fashion. You may try using the division algorithm on n, and expressing it as n=qm+r; then try to prove that (n,m)=(r,m).

 

[kingwinner]

hmm...sorry I don't understand. What do you mean by "Coprimes repeat in a kind of 'modular' fashion"?

 

[CRGreathouse]

hmm...sorry I don't understand. What do you mean by "Coprimes repeat in a kind of 'modular' fashion"?

If c is coprime to m, then c+m is coprime to m, and in general c+km is coprime to m.

 

[blue_raver22]

I understand your curiosity and desire for proof. The Euler's phi function, also known as the totient function, is a fundamental concept in number theory that has been studied and proven by many mathematicians over the years. It is defined as the number of positive integers less than or equal to a given integer m that are relatively prime to m (meaning they share no common factors other than 1).

To prove the statement you mentioned, we can use the fundamental theorem of arithmetic, which states that every positive integer can be uniquely expressed as a product of prime numbers. Let's consider a specific case where m=6 and k=3. This means we are looking at the numbers 1 to 18 (mk=6x3=18) and we want to find the number of integers that are relatively prime to 6.

Using the fundamental theorem of arithmetic, we can write 6 as 2x3. This means that any number that shares a common factor with 6 must also have either 2 or 3 as a factor. Therefore, the numbers that are not relatively prime to 6 are 2, 3, 6, 12, and 18. This gives us 5 numbers that are not relatively prime to 6.

Now, let's look at the numbers that are relatively prime to 6. These numbers cannot have 2 or 3 as a factor. So, out of the 18 numbers we are considering, we can eliminate every second number (since they will have 2 as a factor) and every third number (since they will have 3 as a factor). This leaves us with 12 numbers that are relatively prime to 6.

We can see that 12 is indeed kφ(m) = 3xφ(6) = 3x2 = 6. This confirms the statement that the number of integers n such that 1≤n≤mk and (n,m)=1 is kφ(m).

In general, this pattern holds true for any positive integers m and k. The proof is more complex and involves concepts such as modular arithmetic and group theory. However, the idea remains the same - the number of integers relatively prime to m is determined by the prime factors of m and is given by the Euler's phi function.

I hope this explanation helps clarify the statement and its proof. Mathematics is a beautiful and fascinating subject, and it is always a pleasure