# Tagged Questions

25 views

### variation of the Euler $\phi$ function?

Let $n \leq m$ be positive integers. Is there a function or expression giving the cardinality of the set $\{r \in \mathbb{Z}^+| 1 \leq r \leq m, \gcd(r,n) = 1 \}$? If $n = m$, it's just $\phi(n)$.
62 views

### prove that $\phi(xy) =\phi(x)\phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. [duplicate]

Prove that $\phi(xy) = \phi(x) \phi(y)$ for any $x$ and $y$ with $(x, y) = 1$. I understand the concept, and have done several examples proofing this but cannot put it in "proof form" because unless ...
81 views

### Without using group theory, How to Prove $n|\phi(a^n-1)$, where $\phi$ is Euler's Totient function. [closed]

Let $\phi$ be Euler's Totient funcion, how to prove this property? If possible can we have an elementary proof without leveraging the group theory? $$n|\phi(a^n-1), \forall n,a>1, \gcd(a,n)=1$$ ...
48 views

### suppose a>1 is an integer, and p is an odd prime number.

Suppose $a>1$ is an integer, and $p$ is an odd prime number. Prove that each odd prime factor of $(a^p)-1$ which does not divide $a-1$ should be in the form $2pt+1$. My Approaching: ($a^p)-1$ is ...
38 views

### Euler totient of a number

If $n= \prod_{i=1}^{m} p_i$, all $p_i$ pairwise distinct, then number of coprimes below $n$ is $\prod_{i=1}^{m} (p_i-1)$. For example with $m=2$, there are $p_2-1$ multiples of $p_1$ below $n$ and ...
34 views

### Solution for generalized Euler's Theorem $a^m\equiv a^{m-\phi(m)} \pmod{m}$?

The above identity holds for any integer $a$. Since my solution(?) does seem neither elegant nor rigorous enough, I want to get some advice to improve it. My solution: If $(a,m)=1$, this identity is ...
33 views

### $n\phi(n)$ with $\phi$ the totient function

How do I prove this theoreme I found on the Wikipedia article of Euler's totient function: $$\frac{1}{2}n\phi(n)=\sum_{\begin{matrix}1\leq k \leq n \\ \gcd(k,n)=1\end{matrix}} k$$ I am aware, that ...
465 views

### New identity for Euler's Totient Function?

A few weeks ago I discovered and proved a simple identity for Euler's totient function. I figured that someone would have already discovered it, but I haven't been able to find it anywhere. So I was ...
13 views

### Schemmel Totient Functions in Literature

I know how to prove that the Schemmel Totient functions are multiplicative, but I was wondering if someone could give me a reference to a place in the literature where such a proof is given.
75 views

### Prove that if d = gcd(m,n) then $\phi(mn)=\phi(m)*\phi(n)/d$ [duplicate]

So if m and n are relatively prime, then the $\phi(mn)=\phi(m)*\phi(n)$ but what happens when $d > 1$?
11 views

### If $p^a \equiv -1 \pmod {q^b}$, is there anything that we can say about $a$ if $p,q$ are odd primes and $a,b > 1$

If $p^a \equiv 1 \pmod {q^b}$, then, from Carmichael's Theorem, we know that: $a = u\varphi(q^b) = u(q-1)(q^{b-1})$ where $u \ge 1$ Can we say anything similar if $p^a \equiv -1 \pmod {q^b}$
80 views

### What is known about the solutions to $\varphi(a)+\varphi(b)=\varphi(a+b)$?

As of late I have been researching Euler's Totient function. For the last week or so I have specifically been studying the equation: $\varphi(a)+\varphi(b)=\varphi(a+b)$ While the equation ...
40 views

### Method for estimating euler phi without knowing the actual factors.

Is there any method to calculate Euler's totient function $\varphi$ without actually factorizing the number. Estimation of $\varphi$ or determining the range in which its value will lie for a given ...
25 views

160 views

### Summation involving totient function: $\sum_{d\mid n} \varphi(d)=n$ [duplicate]

Prove that:$$\sum_{d\mid n} \varphi(d)=n$$ Where $\varphi(n)$ denotes the number of positive integers $m$ less than or equal to $n$ such that $\gcd(m,n)=1$ I am lost here, any help would be ...
148 views

### On proving $n = \sum_{d\mid n}\varphi(d)$

$\def\nset{\{1,\dots,n\}}$ I'm trying to work out my own proof1 of Euler's classic formula $$n = \sum_{d\mid n}\varphi(d)\;.$$ I'm looking for some pointers to the standard terminology and/or ...
69 views

### Observations needed to justify an algebraic passage in proof of a property of $\varphi$ (Totient function)

Let $\varphi$ be the Euler's totient function and let $n\in \mathbb{N}$ be factorized in primes as $n=p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_l^{\alpha_l}$. I was looking for alternative methods to ...
35 views

### Totient function: show that numbers are equal [duplicate]

I am a bit lost. It seems to be true, but I am not sure how to prove this to myself. If $m*ϕ(m)=n*ϕ(n)$ then $m=n$ It is clear that this property would hold if m and n were prime, but I am not sure ...
26 views

### Totient function inequality

I am not quite sure how to approach this problem: If a and n are such natural numbers that a divides n, then $n-ϕ(n)\ge a-ϕ(a)$ This is my thought process so far: Obviously the fact that $n=n*a$ ...
105 views

68 views

### Question about the totient function and congruence classes

If $x,y$ are integers where $x | \varphi(y)$ does it follow that the reduced residue class modulo $y$ divides evenly into congruence classes modulo $x$? For example, if we look at $y=35$ and $x = 3$. ...
78 views

### Show that there does not exist an integer $n\in\mathbb{N}$ s.t $\phi(n)=\frac{n}{6}$

Show that there does not exist an integer $n\in\mathbb{N}$ s.t $$\phi(n)=\frac{n}{6}$$. My solution: Using the Euler's product formula: $$\phi(n)=n\prod_{p|n}\Bigl(\frac{p-1}{p}\Bigr)$$ We have: ...
59 views

### Euler's Totient Function Problem with my Understanding

Solve φ36 List of relatively prime numbers: 1,2,3,4,6,9,12,18,36 So from this I would say that φ36 = 9, but using an online calculator I got it to be 12. Where am I going wrong?
401 views

### Properties of the euler totient function

Why is it that the euler totient function has the following condition true based on its definition? $$\phi(p^k)=p^{k-1}(p-1) = p^k(1-\frac{1}{p}) = p^k-p^{k-1}$$ A proof would be awesome and an ...
98 views

### Define ≡ in this situation?

"Determine $d$ as $d^{-1} \equiv e \bmod \phi(n)$, i.e., $d$ is the multiplicative inverse of $e \bmod \phi(n)$." (number $5$). I'm looking at this, and i'm not sure what the $\equiv$ means in this ...
42 views

### Prove that $\varphi(n) = n \cdot \prod\limits_{i=1}^l(p_i - 1) / p_i$

In a course on cryptography we should prove that if $n$ is of the form $p_1^{k_1} \cdot \ldots \cdot p_l^{k_l}$ and $p_1, \ldots, p_l$ are all distinct prime numbers then ...
83 views

### Proof that the euler totient function is multiplicative, correctness?

I've tried proving that $\varphi(mn) = \varphi(m)\varphi(n)$ (if $gcd(mn)=1$). The proof I try to setup doesn't look like the proof I find in textbooks, where am I going wrong? Proof: We try to ...
76 views

### Suppose that n > 1. Prove that n divides $φ (2^n - 1)$ . [duplicate]

Suppose that n > 1. Prove that n divides $φ(2^n - 1)$ . Hint: Show that 2 has order n mod $2^n - 1$
146 views

### $2730\mid n^{13}-n\;\;\forall n\in\mathbb{N}$

Show that $2730\mid n^{13}-n,\;\;\forall n\in\mathbb{N}$ I tried, $2730=13\cdot5\cdot7\cdot2$ We have $13\mid n^{13}-n$, by Fermat's Little Theorem. We have $2\mid n^{13}-n$, by if $n$ even ...
53 views

### I suppose $(a,m)=(a-1,m)=1$, show that $1+a+a^2+\ldots+a^{\phi(m)-1}\equiv0\pmod m$

I suppose $(a,m)=(a-1,m)=1$, show that $$1+a+a^2+\ldots+a^{\phi(m)-1}\equiv0\pmod m$$ I tried $$1+a+a^2+a^{\phi(m)-1}=\frac{a^{\phi(m)}-1}{a-1}$$ I believe that this equality that put up help, ...
163 views

### For every positive integer n greater than $2$, $\phi(n)$ is an even integer.

Theorem: For every positive integer n greater than $2$, then $\phi(n)$ is an even integer. I know this theorem and the same is used much, but I was curious how it would be to demonstrate it, show ...
184 views

### Euler's totient function and gcd

If p is a prime and $\phi(ap)=\phi(a)\phi(p)$ can one conclude that a and p are relatively prime? I need to show that p does not divide a, but I'm not sure if $\phi(ap)=\phi(a)\phi(p)$ is enough to ...
29 views

### Phi-Function Congruence

Let n be a positive integer such that $n>1$. Show that for any positive a, $a^{n}\cong a^{n-\phi(n)}$ mod n. I think that this needs the fact that if positive integers x,y with $y>1$ then ...
114 views

### If $n = 2 \varphi(n)$, then $n = 2^j$ for some positive integer $j$.

Let $n$ be a positive integer such that $n=2\varphi(n)$. Show that $n=2^j$ for a positive integer $j$. Basically I'm completely stumped on this question, I have no idea where to begin or what to ...
98 views

776 views

### Euler Totient Function- proof of $\phi(n) = n(1-1/p_1)(1-1/p_2)…(1-1/p_k)$

Now I have come across a proof of the function using the inclusion-exclusion principle however it isn't so clear how they easily have factorized in the end to get ...
### Show $\sum\limits_{d|n}\phi(d) = n$. [duplicate]
Show $\sum\limits_{d|n}\phi(d) = n$. Example : $\sum\limits_{d|4}\phi(d) = \phi(1) + \phi(2) + \phi(4) = 1 + 1 + 2 = 4$ I was told this has a simple proof. Problem is, I can not think of a way to ...
### How many products of two single digits $x,y$ end in a specific digit $n$ in a given base $b$?
While one can use brute force (i.e. counting a multiplication table) to see that e.g. in base ten there are 27 combinations yielding zero ($0\cdot n, 2n\cdot 5$ and the other way around, counting ...