Questions on the totient function $\phi(n)$ (sometimes $\varphi(n)$) of Euler, the function that counts the number of positive integers relatively prime to and less than or equal to $n$.

learn more… | top users | synonyms (1)

0
votes
0answers
15 views

what can we say about $\varphi^{-1}(2^a), \varphi^{-1}(2^\alpha), \varphi^{-1}(2^\beta)$ where $a=\alpha+\beta$?

Let us consider the Euler's totient function $$\varphi(n):=\#\{1\leq r\leq n: \gcd(r,n)=1\}$$ We also know that $$\varphi(mn)=\varphi(m)\varphi(n)\frac{d}{\varphi(d)}$$ where $d=\gcd(m,n)$. Now ...
-3
votes
0answers
35 views

Eulers Phi Function [on hold]

I need help with Verify that Eulers phi function gives a result of $40$ when applied to the numbers $75$. I know that $\phi(40) = 16$, $\phi (75) = 40$ Please help?
-2
votes
1answer
45 views

Dealing with phi function property

If $n=2^kN$, where $N$ is odd, then $$\sum_{d\mid n}(-1)^{n/d}\phi(d)=\sum_{d\mid 2^{k-1}N}\phi(d)-\sum_{d\mid N}\phi(2^kd)$$ I have no idea how to seperate things inside the left side. In a ...
2
votes
0answers
21 views

Euler totient divisor sum [duplicate]

To prove this identity, $$\sum_{d \mid n}\phi(d)= n \qquad \text{for} \, n=1,2,3,\ldots$$ where $\phi (n)$ is the Eulers totient function, I tried this by breaking it into two parts, n is either an ...
1
vote
0answers
14 views

Cracking any linear congruential generator

I have a linear congruential generator $X_{n+1} = (aX_n + b) \bmod 2^k $with given arguments and number $Y$. The problem is to find the smallest $i$ that $X_i = Y$ or tell that there is no such $i$. ...
3
votes
0answers
19 views

Product of the Euler phi function [duplicate]

Prove the following statement: If $n, m\in\mathbb{Z} $ and $g=$gcd$(n, m) $ then is $$\varphi(m, n) =\frac{ \varphi(m) \varphi(n) g} {\varphi(g)}. $$ Hint: Prove the statement with induction above ...
0
votes
0answers
40 views

Ensuring all $n$ in $\varphi(n)=x$

For Euler's totient function $\varphi(n)=x$ and any single known $x$, how can I prove that a set of $n$'s is complete? For instance, given $x=28$, $n\in\lbrace29,58\rbrace$. How to prove that no ...
0
votes
0answers
13 views

$Φ_n$ is Euler group, $n> 2$ is an integer, and $m$ the number of solutions of the equation $x^2 = 1$ in the ring $Z_n$.

Prove $$\prod_{i ∈ Φ_n} i=(-1)^{\frac{m}{2}}$$ Then what becomes this identity if $n$ is a prime number? I know that if $x^2=1$, we pair the number with its inverse modulo $n$ in the ...
2
votes
3answers
55 views

Find all $x \in \mathbb{N}$ that satisfy $pφ(x)=x$, where $p$ is a prime.

Find all $x \in \mathbb{N}$ that satisfy $pφ(x)=x$, where $p$ is a prime. This is a generalization of Solve the equation $2φ(x)=x $ for $x\in\mathbb N^+.$, where this is solved for $p=2$. My ...
1
vote
2answers
69 views

Solve the equation $2φ(x)=x $ for $x\in\mathbb N^+.$ [duplicate]

Solve the equation $2φ(x)=x $ for $x\in\mathbb N^+.$ I know $$x=\prod_\limits{i} p_i^{a_1} =p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3} \ldots p_n^{a_n}$$ ...
1
vote
2answers
51 views

Solve the following equations for $x, (x ∈ N^+) (a)\ 2φ(x) = x; (b)\ 3φ(x) = x; (c)\ 4φ(x) = x.$

Solve the following equations for $x, (x ∈ N^+)$ $$ (a)\ 2φ(x) = x;$$ $$(b)\ 3φ(x) = x;$$ $$(c)\ 4φ(x) = x.$$ Can anyone help me with this, or give me some hint?
2
votes
2answers
52 views

Calculate φ(36), where φ is the Euler Totient function. Use this to calculate 13788 (mod 36).

Hello I am wondering if any one can help me I am trying to figure out how to Calculate $φ(36)$, where $φ$ is the Euler Totient function. Use this to calculate $13788$ $(mod 36)$. I have an exam ...
2
votes
3answers
51 views

Is $a_n=\frac{1}{n}\sum_{k=1}^n\frac{\varphi(k)}{k}$ convergent?

Let $(a_n)_{n\in\mathbb{N}}$ be defined as $a_n=\frac{1}{n}\sum_{k=1}^n\frac{\varphi(k)}{k}$ where $\varphi$ is the euler totient function. Is $(a_n)$ convergent. If so, what is its limit? I have ...
1
vote
1answer
51 views

Let $d=(m,n)$. Prove: $φ (mn) = φ (m) φ (n)\frac{d}{φ (d)}$ [duplicate]

Let $d=(m,n)$. Prove: $$φ (mn) = φ (m) φ (n)\frac{d}{φ (d)}$$ Can anyone help me with this proof?
1
vote
2answers
25 views

Let $m$ be the smallest positive integer such that $a^m \equiv 1 \pmod n$

Let $n \in \mathbb{N}$, $a$ an integer and $\gcd(a, n) = 1$. Further, let $m$ be the smallest positive integer such that $$a^m \equiv 1 \pmod n.$$ Prove that $m$ divides $\phi(n)$. Can anyone help ...
2
votes
1answer
94 views

Euler`s Theorem and Diophantine Equations

Euler`s Theorem says that for all coprime intergers $a,b$ $a^ {φ(b)} \equiv 1 \pmod b$. This implies that for any $z,x$ which satisfies $\gcd(x,y)=\gcd(z,y)=1$ $x^{φ(y)}-z^{φ(y)} \equiv 0\pmod y$ ...
2
votes
2answers
28 views

Sum and product of coprimes?

Let's say $m_{1}, m_{2}, m_{3},...,, m_{\phi (m)}$ are the numbers which are coprime to $m$. $m_{i}< m$ , $i=1,2,..,\phi (m)$, $\phi (m)$ is the Euler's totient function. How to find sum and ...
0
votes
1answer
37 views

For what values of n does $\phi(n) = \frac{n}{3}$ [duplicate]

I begun by splitting up n into its prime factors and using the multiplicative property of the totient function. But i couldnt see where to go from there.
2
votes
0answers
39 views

Finding a summation involving gcd

I am trying to evaluate the following sum: $$b\sum_{i=a}^b\frac{i}{\gcd(i,b)}$$ I have solved the problem if $a=1$ but I am clueless for the case when $a$ is not $1$. For $a=1$, I used the fact that ...
1
vote
1answer
50 views

Proof any arithmetic progression coprime count same as toting function of n

Euler's totient function of n gives us the number of integers coprime to n that are less than or equal to n and greater than or equal to 1. Clearly the arithmetic progression {d, 2d, ..., nd} with ...
6
votes
3answers
336 views

About phi function

Find all positive integers n such that $ \phi(n) |n $ I find $n=2^k ,2^k ×3^j$ is answer ,I can't find another answers.
2
votes
1answer
59 views

Fast modular exponentiation when Euler's Theorem doesn't apply

I want to write an algorithm to reasonably efficiently calculate $a^L \pmod n$ where $a$ and $n$ are reasonably small (ten digits or so), and $L$ is unreasonably large (billions of digits). I can ...
7
votes
1answer
54 views

Separating numbers prime with $n$ in fixed length intervals .

This question ( Proving for $n \ge 25$, $p_n > 3.75n$ where $p_n$ is the $n$th prime. ) led me to ask the following . Take $n>2$ a positive integer . Let $a_1,a_2,\ldots,a_{\phi(n)}$ be all ...
1
vote
5answers
42 views

Exponents and mod (Euler's theorem)

I know how to compute $7^{402} \pmod{10}$ using Euler's theorem since $7$ and $10$ are relatively prime. But is there an easy way without using a calculator to compute $12^{720} \pmod{10}$. I don't ...
5
votes
5answers
584 views

Why aren't there any solutions?

I am trying to find an answer to the following congruence: $$x^{81} \equiv 95 \pmod{126}$$ And i couldn't find any soltuon but I don't know why. First I though about the prime factorization for ...
1
vote
2answers
35 views

Prove that for all primes p: $φ(p^i)$= $p^i$ - $p^{i-1}$

Prove that for all primes p: $φ(p^i)$= $p^i$ - $p^{i-1}$ I found a proof on the wikipedia article of the Euler's totient function. But I cannot understand it, as it's been many years since I dealed ...
1
vote
0answers
35 views

Number Theory: Find a primitive root of $13^{901}$ and find a complete set of primitive roots of $13$

I solved this problem: Find a complete set of mutually incongruent primitive roots of $13$. I know that there are $\phi(\phi(13))=4$ primitive roots of 13, which are $2,6,7,$ and $11$. However, I ...
2
votes
2answers
50 views

Why $Gal(\mathbb Q(\zeta _n)/\mathbb Q)\hookrightarrow (\mathbb Z/n\mathbb Z)^\times $

Let $\zeta _n=e^{\frac{2i\pi}{n}}$ an let $\mu_n=\{1,\zeta _n,\zeta _n^2,...,\zeta _n^{n-1}\}$. 1) Show that $\mathbb Q(\mu_n)=\mathbb Q(\zeta _n)$ and that $\mathbb Q(\zeta _n)/\mathbb Q$ is ...
0
votes
0answers
22 views

Totient euler function: Why $\gcd(n,k)=1$ is important for $\zeta _n^k$.

Let $\mu_n=\{\zeta \mid \zeta^n-1=0\}=\{1,\zeta _n,\zeta _n^2,...,\zeta _n^{n-1}\}$. We call generator an element $\zeta_n^k$ when $\gcd(k,n)=1$. Why those number are such important ? I think that ...
1
vote
0answers
24 views

Large Number Modulo Computation

Compute the following: a) $2^{208} \pmod{53}$ b) $2^{288} \pmod{73}$ c) $7^{19} \pmod{28}$ Here is what I did so far: a) ∅ (53) = 52 $(2^{52})^4 => (1)^4 ...
0
votes
2answers
14 views

Show that $|(\mathbb Z/p^n\mathbb Z)^* |=p^n-p^{n-1}$.

I'm trying to show that $|(\mathbb Z/p^n\mathbb Z)^* |=p^n-p^{n-1}$. Then, $$(\mathbb Z/p^n\mathbb Z)^*=(\mathbb Z/p^{n}\mathbb Z)\backslash \{i\mid \gcd(i,p^n)\neq 1\}$$ So I guess that $$|\{i\mid ...
5
votes
0answers
47 views

About the sum $ s_n:=\sum_{k=1}^{n} \text{lcm}(k,n) $

I'm currently studying the following sum: $$ s_n:=\sum_{k=1}^{n} \text{lcm}(k,n) $$ I manipulated it as follows: $$\begin{align} s_n&=\sum_{k=1}^{n} \text{lcm}(k,n)\\ ...
0
votes
1answer
33 views

Solve the linear congruence: $2^{2015}x\equiv 1\pmod {13}$

Solve the linear congruence: $2^{2015}x\equiv 1\pmod {13}$ $x\equiv (2^{2015})^{\phi(13)-1}\equiv (2^{2015})^{12-1}\equiv 2^{22165}\equiv y\pmod{13}$ $22165=13\cdot 1705$ $y=2^{13} $ or ...
2
votes
0answers
43 views

A property of primes and odd numbers

I was looking at the totient function, and I found the property that $pq-\phi(pq)$, where $p$ and $q$ are primes, can give you any odd number. It is trivial to prove this for primes, because ...
2
votes
1answer
31 views

Euler's Totient Function and a Subset of Z/nZ

Suppsoe we are given an integer $n$. Define \begin{align*} \psi \left( n \right) = \left| \left\{ a \in \mathbb{Z}/ n\mathbb{Z}^\times \vert a^{n-1} \neq 1\right\} \right| \end{align*} Show: if $\psi ...
1
vote
3answers
55 views

Why is the sum across divisors of the Mobius function times the Euler function equal to zero when n is even?

I want to show that when $n$ is even, $$\sum_{d|n} \mu(d)\varphi(d) = 0.$$ I've played around with it for a while but I can't seem to get it.
0
votes
2answers
25 views

Proof of Euler's Theorem with groups

I read that in order to prove it using groups, we can see that the order of the group of units is equal to Euler's totient function: $$|U(n)|= \phi (n)$$ After this, however, the author goes on to ...
2
votes
1answer
85 views

On the many patterns of Euler totient function manipulations

The full title for this question should be On the many patterns of Euler totient function manipulations and their tendency towards symmetry at primorials, (but didn't want to take up too much room). ...
8
votes
1answer
97 views

$n\cdot \phi(n)=m\cdot \phi(m)$

If I am not mistaken here in OEIS says that $n\cdot \phi(n)=m\cdot \phi(m)$ is possible only if $n=m$. $\phi(n)$ denotes Euler's totient function. Is there a proof of this fact?
2
votes
1answer
34 views

Why is the totient function expressed as $\phi(n)=n \prod_{p|n}\left ( 1-\frac{1}{p} \right )$

This seems a little inconvenient, and using $$\phi(n)=\prod_{p|n} \left ( p-1 \right )$$ seems much more convenient for computational purposes. So I am guessing that there is a specific reason ...
0
votes
1answer
63 views

Euler's totient function and related sum

I am supposed to calculate the following sum : $\sum _{d|n} (n/d) * \phi (n/d)$ where the sum is over all divisors (d) of a given number (n) and $\phi (x)$ is Euler's totient function . Since the ...
1
vote
1answer
53 views

If $n$ satisfies $\left(-3+\sqrt{1+8n}\right)\sigma(n)=4\left(-1+\sqrt{1+8n}\right)\phi(n)$ then is an even perfect number?

Let an integer $m\geq 1$, and $\sigma(m)$ is the sum of positive divisors function, and $\phi(m)$ is Euler's totient function, counting the number of integers $1\leq k\leq m$ such that $gcd(k,m)=1$ ...
0
votes
1answer
50 views

Eulers Phi function with list of distinct perfect numbers

Prove that $\phi(n_1 n_2 \cdots n_m)$ = $2^{m-1}\cdot \phi(n_1)\cdot\phi(n_2) \cdots \phi(n_m)$ where all of the $n$'s are distinct even perfect numbers. I thought that because $\phi(2^k) = 2^{k-1}$ ...
1
vote
1answer
27 views

Number Theory: Prove that for any $n\exists k$ such that $n\mid\phi(k)$.

I think I've proven this homework problem, but I'm not sure if my proof is correct: Given an integer $n$, prove that there exists at least one $k$ for which $n\mid \phi(k)$. (Where $\phi$ is the ...
2
votes
4answers
162 views

Number Theory: Find all solutions of $\phi(n)=16$ and $\phi(n)=24$

I have this homework problem assigned and I'm a little confused in solving it: Find all solutions of $\phi(n)=16$ and $\phi(n)=24$ (where $\phi(n)$ is the Euler phi-function). The hint that's ...
1
vote
2answers
41 views

What is the remainder of $31^{2008}$ divided by $36$?

What is the remainder of $31^{2008}$ divided by $36$? Using Euler's theorem, we have: $$ \begin{align*} \gcd(31,36) = 1 &\implies 31^{35} \equiv 1 \pmod{36} \\ &\implies 31^{2008} \equiv ...
0
votes
1answer
39 views

How to find reminder of $m^{x}$ divided by $n$ using Euler's and Fermat's little theorem

How do you find reminder of $m^{x}$ divided by $n$ using Euler's and Fermat's little theorem? Can anyone show me step-by-step how to apply Fermat's little theorem and Euler's theorem? Example: What ...
1
vote
1answer
46 views

Have i understood Fermat little theorem and Euler's theorem correctly?

Why: to make modulo and power calculations easier ! I will take an example to show my thoughts on Fermats Little theorem , Assume we want to calculate $3^{31}( mod 7)$ We see that $7$ is prime ...
2
votes
1answer
61 views

Mobius function vanishes over sum of totient numbers

Let k be a positive integer. I need to prove that the sum $$\sum_{n \in \mathbb{N} : \phi(n)=k} \mu(n)=0$$ where $\phi$ is the Euler Totient function and $\mu$ is the Mobius function. Here is what I ...
2
votes
2answers
70 views

Proving the Converse of Euler's Totient Theorem

Euler's Totient Theorem states that if $n$ and $a$ are coprime positive integers, then $$a^{\varphi (n)} \equiv 1 \pmod{n}$$ Wikipedia claims that the converse of Euler's theorem is also true: if ...