# Tagged Questions

3answers
144 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 ...
2answers
115 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?
1answer
103 views

### Finding All Integers in such that $\phi(n)=80$

I don't know where to start with this problem so please help. The problem is: Find all integers n such that $\phi(n) = 80$.
1answer
46 views

### Why is this fact about the totient function true? [duplicate]

$\displaystyle \sum_{k<n}_{gcd(k,n)=1}k = \frac{1}{2} n \phi(n)$ This is a homework problem. I would ideally like to get to the final proof on my own. But at the moment I can't even decide how to ...
2answers
52 views

### Totient function and Euler's Theorem

Given $\big(m, n\big) = 1$, Prove that $$m^{\varphi(n)} + n^{\varphi(m)} \equiv 1 \pmod{mn}$$ I have tried saying $$\text{let }(a, mn) = 1$$ $$a^{\varphi(mn)} \equiv 1 \pmod{mn}$$ ...
1answer
150 views

### Modified Euler's Totient function for counting constellations in reduced residue systems

I am working on a modified totient function for counting constellations in reduced residue systems for the same range that Euler's totient function is defined over. This post is separated into three ...
0answers
91 views

### Partition minimizing maximum of Euler's totient function across terms

Given natural numbers $M$ and $N$, I'd like to find a partition of $2^N$ with $M$ or fewer terms, $t_1 + t_2 + ... + t_M$, such that $\max(\phi(t_1), \phi(t_2), ..., \phi(t_M))$ is minimized, where ...
2answers
125 views

### Problems with Euler $\phi$ function (2)

If $a$, $b$ are coprime, then $$a^{\phi(b)}+b^{\phi(a)}\equiv 1 \bmod (ab) \, .$$ If $\left(n=2\phi(n)\right)$, then $n$ is a power of $2$.
2answers
157 views

### Is my shorter expression for $s_m(n)= 1^m+2^m+3^m+\cdots+(n-1)^m \pmod n$ true?

I'm considering the following sums for natural numbers n,m $$s_m(n)= \sum_{k=1}^{n-1} k^m =1^m+2^m+3^m+\cdots+(n-1)^m$$ modulo n . Looking at odd n first, I found by analysis of the pattern of ...
1answer
171 views

### Seeking a proof of $\sum_{d|n}\phi(\frac{n}{d})a^d\equiv 0 \mod{n}$, where $\phi$ is the Euler Totient Function.

I need to prove the proposition. Let $a$ be an arbitrary integer. Then for every positive integer $n$, we have $$\sum_{d \mid n}\phi\left(\frac{n}{d}\right)a^d\equiv0\pmod{n}.$$
3answers
268 views

### Properties of Euler's $\phi()$ function

This is part of the $\phi(mn) = \phi(m)\cdot \phi(n)$ theorem. For some integer $a$ relatively prime to $m\cdot n$ how do I know the following: $a\mod m$ is relatively prime to $m$ $a \mod n$ is ...
0answers
47 views

### (Please check working) Given RSA encoding function $E: x\to x^{11} \pmod{3737}$ find the decoding function $D$

Please check the working and final answer to the question: Question: Given RSA encoding function $E: x\to x^{11} \pmod{3737}$ find the decoding function $D$ My working: \$\phi(3737) = \phi(37) \times ...
3answers
85 views

### Given RSA encoding function $E: x\to x^7 \pmod{6161}$ find decoding function D

So far I got: $7\alpha \equiv 1$ mod $\phi(6161)$ $\phi(6161) = \phi(61) \times \phi(101) = 6000$ $7\alpha \equiv 1$(mod $6000)$ At this point we are supposed to do euclid's algorithm and somehow ...
0answers
232 views

### Induction in proof of multiplicativity of Euler totient function

(Updated below) I'm working through John Stillwell's Elements of Algebra, and while his exercises are generally crafted to be not too difficult, there's one that I don't even understand what it's ...
2answers
93 views

### Show that $c^{\varphi(m)/2} \equiv 1 \pmod{m}$ if $m$ has two odd prime divisors

The following problem is one of the exercises in Topics in the Theory of Numbers (Erdős et al.) Show that if the positive integer $m$ has at least two distinct odd prime divisors, and $c$ is ...
5answers
966 views

### What's the proof that the Euler totient function is multiplicative?

That is, why is $\varphi (A\cdot B)=\varphi (A)\cdot \varphi (B)$, if A and B are coprime? It's not just a technical trouble—I can't see why this should be, intuitively: I bellyfeel that its ...
3answers
312 views

### Does knowing the totient of a number help factoring it? [duplicate]

Possible Duplicate: Factoring a number $p^a q^b$ knowing its totient Edit: The quoted question addresses only numbers of the form $p^a q^b$, I asked a general question for arbitrary $n$. ...
2answers
153 views

### Solutions of $\phi(x)=n$ for a given n.

I need to prove for a given n, if $\phi(x)=n$ has a solution for x, it always has another? We know $\phi(2)=\phi(1)=1$ and can easily prove that n must be even for x>2. So, n can be of the form ...
3answers
467 views

### $\phi(n)=\frac{n}{2}$ if and only if $n=2^k$ for some positive integer k

Show that $\phi(n)=\frac{n}{2}$ if and only if $n=2^k$ for some positive integer k. I think I have it figured and would like to see if I am on the right track. Thank you.
0answers
188 views

### Sum of floor function $\pmod{n}$

Let $n$ be a positive integer. Let $a$ be a nonzero integer such that $\gcd(a,n)=1$. How to show that \frac{a^{\phi (n)}-1}{n} \equiv \sum_i \frac{1}{ai} \left \lfloor \frac{ai}{n} \right \rfloor ...
1answer
464 views

### Show that $\phi(mn) = \phi(m)\phi(n)\frac{d}{\phi(d)}$ [duplicate]

Possible Duplicate: Proof of a formula involving Euler's totient function. For positive integers $m$ and $n$ where $d=gcd(m,n)$, show that \phi(mn) = ...
2answers
158 views

### How to prove $n*\varphi(n)/2$ sum?

how do I prove The second formula from Euler's totient function ? $$\sum_{\substack{1\le k\le n\\(k,n)=1}} k=\frac 12 n \varphi(n)$$ for $n>1$.
1answer
113 views

### How to show $\varphi (ab) = d\varphi(a)\varphi(b) / \varphi(d)$? [duplicate]

Possible Duplicate: Proof of a formula involving Euler's totient function. I have this interesting question that I have difficulty to prove. I know that: $\gcd(a,b) = d$ And I need ...
2answers
140 views

### If $n=2\phi(n)$, then $n=2^j$.

I need to show that if $n=2\phi(n)$, then $n=2^j$, where $n,j\in\mathbb{N}$. I have a strong feeling that this can only be shown by contradiction. Therefore, I assumed that both $n=2\phi(n)$ and ...
2answers
2k views

### Find all positive integers $n$ such that $\phi(n)=6$.

I am asked to find all positive integers $n$ such that $\phi(n)=6$, and to prove that I have found all solutions. The way I am tackling this is by constructing all combinations of prime powers such ...
2answers
551 views

### How to prove $\phi(n) = n/2$ iff $n = 2^k$?

How can I prove this statement ? $\phi(n) = n/2$ iff $n = 2^k$ I'm thinking n can be decomposed into its prime factors, then I can use multiplicative property of the euler phi function to get the ...
2answers
617 views

### How to prove $\phi(mn) > \phi(m)\phi(n)$ if $(m,n) \ne 1$

I need to prove that $$\phi(mn) > \phi(m)\phi(n)$$ if $m$ and $n$ have a common factor greater than 1. I have read up on the case where $m$ and $n$ are relatively prime, then ...
2answers
124 views

### Calculate $a^8 \bmod 15$ for $a = 1,2,\dots,14$

I am trying to calculate $a^8 \bmod 15$ for $a = 1,2,\dots,14$ I get that because $a = 2,4,7,8,11,13,14$ are relatively prime to $15$, the answer will be $1$ in those cases. But how to get this for ...
1answer
263 views

### An approximate relationship between the totient function and sum of divisors

I was playing around with a few of the number theory functions in Mathematica when I found an interesting relationship between some of them. Below I have plotted points with coordinates ...
2answers
194 views

### Nice formula for $\sum\limits_{d|n}(-1)^{n/d}\Phi(d)$?

How do I evaluate $$\sum_{d|n}(-1)^{n/d}\Phi(d)?$$ $\Phi(d)$ is Euler's totient function. Thanks.
2answers
280 views

### Is there a methodical way to compute Euler's Phi function

Is there an algorithmic or methodical way to "factorise" the numbers in euler's phi function such that it becomes easily computable? For example, $\phi(7000) = \phi(2^3 \cdot 5^3 \cdot 7)$ I'm ...
2answers
337 views

### Finding the maximum number with a certain Euler's totient value

Euler's totient function has a lower bound for large values, but is there any way to pick out maximums for specific values of the function? That is, how would I find the maximum number n such that ...
3answers
218 views

### Why is 2 totative of 36?

Based on my understanding, the totient of any number K is the number of relative primes to K, i.e. numbers less than or equal to K that do not share a divisor. Everywhere I look is telling me that 2 ...
2answers
569 views

### Why does $\phi(pq)=\phi(p)\phi(q)$?

In an RSA paper I am reading it is assumed that where $p$ and $q$ are distinct prime numbers: $\phi(pq)=\phi(p)\phi(q)=(p-1)(q-1)$ I would love to know why/how this is so? Is there some way to prove ...
1answer
235 views

### How many irreducible fractions between 0 and 1 have denominator less than $n$?

Or, in an $n\times n$ grid of dots, how many distinct lines pass through at least two of the dots, one of which is the lower left dot? Is there a good way to do this? Thanks.
4answers
1k views

### Identity involving Euler's totient function: $\sum \limits_{k=1}^n \left\lfloor \frac{n}{k} \right\rfloor \varphi(k) = \frac{n(n+1)}{2}$

Let $\varphi(n)$ be Euler's totient function, the number of positive integers less than or equal to $n$ and relatively prime to $n$. Challenge: Prove \sum_{k=1}^n \left\lfloor \frac{n}{k} ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 115, "mathjax_display_tex": 9, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9201138615608215, "perplexity_flag": "head"}