Tagged Questions
6
votes
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 ...
3
votes
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?
1
vote
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$.
1
vote
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 ...
3
votes
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}$$
...
5
votes
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 ...
2
votes
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 ...
4
votes
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$.
11
votes
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 ...
5
votes
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}.$$
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
2
votes
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 ...
3
votes
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 ...
4
votes
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 ...
3
votes
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$.
...
0
votes
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 ...
3
votes
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.
4
votes
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 ...
4
votes
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) = ...
2
votes
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$.
1
vote
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 ...
1
vote
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 ...
2
votes
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 ...
1
vote
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 ...
5
votes
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 ...
-1
votes
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 ...
5
votes
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 ...
5
votes
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.
4
votes
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 ...
4
votes
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 ...
1
vote
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 ...
8
votes
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 ...
3
votes
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.
15
votes
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} ...
