Number Theory Proof Help: Show p-1 & p^(e-1)|∅(n)

[rechinball]

hey guys been staring at this question for a few days and frustratingly nothing springs to mind. If any1 could offer some direction that would be awsome :)

let n be a positive integer, and let p be a prime. Show that if e is a positive integer and p^e|n then p-1|∅(n) and p^(e-1)|∅(n)

 

[mathwonk]

explain your notation and you will likely get more answers.

 

[Deveno]

my guess is he(?) intends to indicate the totient function.

 

[20Tauri]

I'm assuming you're using ∅ to indicate Euler's Totient Function/the Euler Phi-Function.

The definition of the totient function/Euler Phi-Function I learned for a natural number n with prime factorization p1^a1 *p2^a2***pn^an, where some of the exponents may be 0 is:

(p1-1)*p1^(a1-1)*(p2-1)*p2^(a2-1)***(pn-1)*pn^(an-1).

So if you know that p^e divides n, the rest should follow from the definition of the Euler Phi-Function.

 

[blue_raver22]

To prove this statement, we first need to understand the concept of Euler's totient function (∅). This function counts the number of positive integers that are relatively prime to a given integer n. In other words, it counts the number of positive integers less than n that do not share any common factors with n.

Now, let's consider the given information that p^e|n. This means that p^e is a factor of n, or in other words, n is divisible by p^e. Since p is a prime number, it is clear that p^e is the highest power of p that can divide n.

Next, we need to show that p-1|∅(n). This can be done by considering the prime factorization of n. Since p^e is the highest power of p that can divide n, it follows that p^(e-1) is also a factor of n. This means that all the numbers that are relatively prime to n must also be relatively prime to p^(e-1). And since p is a prime number, all the numbers that are relatively prime to p^(e-1) must be less than p, which includes p-1. Therefore, p-1|∅(n).

Similarly, we can show that p^(e-1)|∅(n). Since p^(e-1) is also a factor of n, all the numbers that are relatively prime to n must also be relatively prime to p^(e-1). And since p is a prime number, all the numbers that are relatively prime to p^(e-1) must be less than p, which includes p^(e-1) itself. Therefore, p^(e-1)|∅(n).

In conclusion, we have shown that if p^e|n, then p-1|∅(n) and p^(e-1)|∅(n). This is because all the numbers that are relatively prime to n must also be relatively prime to p^(e-1) and p-1, which are the highest powers of p that can divide n. I hope this explanation helps to clarify the concept and guide you in the right direction.