0
votes
1answer
17 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$?
0
votes
0answers
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}$
5
votes
0answers
67 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 ...
0
votes
0answers
32 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 ...
0
votes
1answer
19 views

I want to prove that if $n$ is composite and $\varphi(n) \mid (n - 1)$, then $n$ is squarefree

I want to prove that if $n$ is composite and $\varphi(n) \mid (n - 1)$, then $n$ is squarefree. To show that $n$ is squarefree in my problem, I want to show there is no prime $p$ such that $p^2 \mid ...
2
votes
4answers
87 views

Prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$.

I want to prove that if $d \mid n \in \mathbb{N}$, then $\varphi(d) \mid \varphi(n)$. It's given that $d \mid n$, so we know that $n = dm$, for some $m \in \mathbb{Z}$. Now, I want to show that ...
6
votes
2answers
85 views

Find all n such that $\phi(n) = n/2$

My idea for the solution is something like this: Since $2 | n$, $n = 2^a p_1^{e1} p_2^{e2} \cdots p_t^{et}$ where $a \geq 1$. Then, $n/2 = \phi(2^a) \phi(p_1^{e1}) \phi(p_2^{e2}) \cdots ...
3
votes
2answers
124 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 ...
5
votes
1answer
128 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 ...
3
votes
2answers
58 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 ...
0
votes
1answer
32 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 ...
1
vote
1answer
24 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$ ...
0
votes
2answers
81 views

Find all integers less than $m$ that are relatively prime to it

Find all integers $n$ between $0\le n < m$ that are relatively prime to $m$, for $m = 4,5,9, 26$. We denote the number of integers $n$ which fulfill the condition by $\phi (m)$, e.g. $\phi (3) = ...
5
votes
4answers
308 views

Euler's totient function of 18 - phi(18)

I am trying to find the phi(18). Using an online calculator, it says it is 6 but im getting four. The method I am using is by breaking 18 down into primes and then multiplying the phi(primes) ...
2
votes
2answers
82 views

Totient function sum over divisors

I would like to know if there is a closed form solution for $$G(n)=\sum\limits_{d\mid n}(-1)^{\frac{n}{d}}\phi(d)$$ It seems quite likely there is since $$\sum\limits_{d\mid n}\phi(d)=n$$ But I ...
3
votes
0answers
46 views

Totient Function problem

Suppose we know that $(m,n)=2$. Show that this implies that $\phi{(mn)}=2\phi{(m)}\phi{(n)}$. My attempt: So let $m=p_1^{r_1}p_2^{r_2}...p_k^{r_k}, n=p_1^{s_1}p_2^{s_2}...p_k^{s_k}$. Then ...
0
votes
1answer
69 views

A restatement of my question about the totient function and congruence classes

I appreciate the answer to my previous question, but I still felt my larger question wasn't answered. So, I am attempting to restate the question more clearly. If $x,y$ are integers where $x | ...
4
votes
1answer
65 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$. ...
1
vote
3answers
76 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: ...
1
vote
2answers
44 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?
3
votes
5answers
294 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 ...
0
votes
2answers
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 ...
0
votes
2answers
41 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 ...
0
votes
1answer
73 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 ...
0
votes
1answer
63 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 $
1
vote
5answers
138 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 ...
1
vote
1answer
41 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, ...
0
votes
5answers
118 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 ...
3
votes
2answers
150 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 ...
0
votes
1answer
26 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 ...
1
vote
5answers
107 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 ...
1
vote
1answer
66 views

Number Theory Help: Eulers phi function, LCM, and Modulos

Assume that $r$ and $s$ are relatively prime positive integers and that $n =rs$. Let $m = \mbox{lcm}(\phi(s), \phi(r))$ and assume that $\mbox{gcd}(a,n)=1$. Prove $$a^m \equiv 1 \bmod{r} \mbox{ ...
3
votes
1answer
66 views

Values for Euler's totient function

How can I prove that the value of $\varphi(p^n-1)$ (where $p$ is prime and $n$ is some positive integer) is some multiple of $n$? The purpose of this is to prove that $n$ divides $\varphi(p^n-1)$.
1
vote
1answer
69 views

Euler Totient clarification

I'm asked to determine what $\varphi{(p^k)}$ is for an arbitrary prime $p$. By definition, $\varphi{(p^k)}=p^k\left(1-\frac1{p}\right)=p^k\left(\frac{p-1}{p}\right)=p^{k-1}(p-1)$. But I thought that ...
3
votes
3answers
141 views

number theory Euler's totient

Prove or disprove: $\phi(n)$ is a perfect square for only a finite number of odd numbers n. I know it works for even numbers since we can use $n=p^k$ and have $p=2$, however, I don't know about odd ...
3
votes
2answers
144 views

Upperbound approximation to the sum of Euler's totient function

I am currently working on a solution to a problem related to the density of finite coprime sets. I believe that I have found a solution to this problem - though it can only be expressed in terms of ...
2
votes
1answer
73 views

What factor has to be applied to $\phi(ab)\propto\phi(a)\phi(b)$ for non-coprime $a,b$?

For $a,b$ coprime, it is known that $\phi(ab)=\phi(a)\phi(b)$. But is there a connection between $\phi(ab)$ and $\phi(a),\phi(b)$ if they are not coprime?
5
votes
3answers
83 views

To what divisors $a$ of $n$ can Euler's Theorem multiplied by $a$ be generalized, i.e. when is $a^{\phi(n)+1}\equiv a \pmod n$?

Euler's Theorem $$a^{\phi(n)}\equiv 1\pmod n,$$ which is valid only iff $a$ and $n$ are coprime, can be "generalized" a bit to $$a^{\phi(n)+1}\equiv a\pmod n, (*)$$ where some zero-divisors of $n$ are ...
1
vote
1answer
640 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 ...
5
votes
5answers
352 views

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 ...
3
votes
2answers
111 views

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 ...
1
vote
1answer
78 views

Measuring the biggest difference in the reduced residue system modulo N

Is there a known means of measuring the biggest difference of consecutive elments of the reduced residue system modulo N? For example, say we have the reduced residue system modulo 15: [1, 2, 4, 7, ...
3
votes
2answers
136 views

On proving the convergence of $1/n^2\sum_{1\le k\le n}\varphi(k)$

Let $$\Phi_n=\frac{1}{n^2}\sum_{k=1}^n\varphi(k).$$ How one can show that $\Phi_n$ is convergent sequence? (Here, $\varphi$ denotes the Euler's totient function.) And please, without any monster ...
0
votes
1answer
49 views

Counting elements of reduced residue systems modulo one number which are smaller than another

Euler's totient function for a prime power input can be written as follows: $$\phi(p_n^k) = (p_n - 1)p_{k-1}$$ This function counts those numbers that are smaller than $p_n^k$ but which are also ...
1
vote
2answers
138 views

Show $r^{\frac{\phi(n)}{2}} \equiv -1$ mod $n$ for a primitive root $r$.

I know that if n has a primitive root, then $x^2 \equiv 1$ has $x \equiv \pm1$ as solutions. This can then be used to show that $r^{\frac{\phi(n)}{2}} \equiv -1$ because $r$ has order $\phi(n)$, and ...
1
vote
1answer
62 views

Is there a proof that no lower bound exists for the totient function?

I read here that there is no lower bound for the totient function. Is there a proof of that?
3
votes
1answer
92 views

Some questions about $\gcd(n,m)$ and $\phi(n)$

I was messing around in Excel at the end of work today and made a table where the $(i,j)$ entry $a_{i,j}$, for $j \geq i$, is 1 exactly when $i$ and $j$ are coprime (see snapshot of a portion of the ...
0
votes
4answers
160 views

Does Euler totient function gives exactly one value(answer) or LEAST calculated value(answer is NOT below this value)?

I was studying RSA when came across Euler totient function. The definition states that- it gives the number of positive values less than $n$ which are relatively prime to $n$. I thought I had it, ...
7
votes
3answers
339 views

Show that the only solution to $\phi(n) =n-2$ is $n=4$

Came across this question in Number Theory. Let $\phi$ denote Euler's totient function; Show that the only solution to $\phi(n) =n-2$ is $n=4$ My workings so far have included, firstly ...
3
votes
3answers
390 views

Find all the natural numbers where $ϕ(n)=110$ (Euler's totient function)

Find all the natural numbers where $ϕ(n)=110$ (Euler's totient function) What the idea behind this kind of questions?