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)

4
votes
1answer
30 views

On factoring and integer given the value of its Euler's totient function.

In an entrance test for admission into an undergraduate course in mathematics the following question was asked. Consider the number $110179$ this number can be expressed as a product of two distinct ...
3
votes
1answer
47 views

Conjecture about odd primes

For each odd prime $p$ there exist $n\in\mathbb{N}$ such that $p\equiv n^2 \text{ (mod }\varphi(n^2))$, where $\varphi$ is Euler's totient function. I'm developing my Forth based computational ...
1
vote
3answers
80 views

Congruence $16^{(x^ 2+x+1)} \equiv 4 \mod 11$

Given the congruence $16^{x^2+x+1}≡ 4 \mod 11$ I'm not necessarily sure how to approach this problem if someone can help me head in the right direction since 16 is not a primitive root of mod 11 I ...
0
votes
0answers
36 views

For a prime p and a positive integer n

we define $A_{p,n} = \{(x,r) : 1 \leq x \leq n \textrm{, r is a positive integer, } p^{r} \textrm{divides x} \}$. Describe the set $A_{p,n}$ for p=5 , n=100. Does the set comprise of ...
0
votes
0answers
41 views

Is there a variant of Euler's theorem for matrices?

Euler's theorem says that whenever $a$ and $p$ are coprime integers, then $a^{\phi(p)} \equiv 1 \mod p$ This is particularly useful for evaluating large powers of $a$: $a^n \ \%\ p = a^{n\ \%\ ...
-1
votes
1answer
48 views

How do I find all n values for which the equation $\phi (n) = 8$ holds? [duplicate]

I've heard all kinds of different ways to solve this problem, yet haven't been able to apply them specifically to the number 8 (Worked fine for 6 for example). I'd love to see a well-explained ...
3
votes
1answer
30 views

How to prove that if the sum of the totatives of two numbers is equal then the numbers are equal?

As the title says, I am trying to prove that if the sum of the totatives of $a$ equals the sum of the totatives of $b$ then $a = b$ but I am stuck. I have that sum of totatives of $n = f(n)= ...
0
votes
1answer
26 views

Calculate Euler inverse function

Given $n$ find all values n such that: $\phi(n) = 26$. I've searched over the web and I've managed to find the lower and upper bounds for n, but i don't know how to go on from this point. I'll be ...
8
votes
2answers
111 views

If $\varphi(x) = m$ has exactly two solutions is it possible that both solutions are even?

If $\varphi(x) = m$ has exactly two solutions is it possible that both solutions are even? Here, $\varphi(x)$ is Euler's phi function, the number of positive integers less than or equal to $x$ ...
0
votes
2answers
28 views

Finding Large Bases with Large Exponents [duplicate]

I'm given the question to find: $151 678 213 ^{115431217}\pmod{10}$ I know that 10 is not prime, so I can't use fermats theoreom. So I've attempted using eulers totient function I know that: ...
0
votes
1answer
49 views

A combinatorial proof of an identity involving Euler’s $ \phi $-function.

My assignment is to prove this: Problem. For an integer $ n \geq 1 $, show that $ \displaystyle n = \sum_{d|n} \phi \! \left( \frac{n}{d} \right) $. I have a hint: Define an equivalence relation ...
5
votes
1answer
264 views

Limit of Euler's Totient function

Clearly if $p$ is prime, the sequence $\frac{\phi(p)}{p} \rightarrow 1$. In general, however, if $s_n \in S \subseteq \mathbb{N}$, we are not even guaranteed of the existence of: $\displaystyle ...
1
vote
0answers
48 views

A difficult question about Runge-Kutta method and Euler's method

I found this question extremely difficult... Especially part b. For part b, I've tried several times. Is it correct that we need to use Taylor expansion to solve it? Since $e'(t) = f(...) + ...
1
vote
1answer
56 views

Euler's $\phi(n)$ function

Find all $n \in \mathbb{N}$ such that $\phi(n) = 4294967296=2^{32}$. I managed to find that $16106127360$, $8589934592$, $10737418240$ and $12884901888$ are solutions for the equation, but I do not ...
3
votes
1answer
66 views

How to show that $\varphi(m_1)=\varphi(m_2)$ gives $m_1=m_2$?

I have solved a problem in number theory which I am providing the details below how I did. Request to all of you, please check it and advise me if I made any mistake. Let $m_1, m_2$ be two odd ...
0
votes
1answer
15 views

$-1$ element in $\mathbb{Z}_n^*$, where $n$ is such that $\mathbb{Z}_n^*$ has a primitive root

Let $n\in\mathbb{N}$ be such that $\mathbb{Z}_n^*$ has a primitive root. Let $a$ be such a primitive root. Is the following true? $$a^{\frac{\phi(n)}{2}}\equiv-1\mod{n}$$ where $\phi$ is Euler's ...
0
votes
0answers
33 views

How to prove this for number theory?

Let $n=p_1^{e1}p_2^{e2}\cdot \cdot \cdot p_k^{ek}.$ Then, $\phi(n)$= $n(1-$ $\frac{1}{p_1})$ (1- $\frac{1}{p_2})$$\cdot \cdot \cdot$ $(1- $ $\frac{1}{p_k})$ Hint: use the following If n has a prime ...
2
votes
1answer
25 views

Perfect numbers of the form $12m+1$ and $\sum_{d\mid n}\frac{1}{\phi(d)}$, where $\phi(m)$ is Euler's totient function

If there are no mistakes combining Exercise 9 a) (Chapter 3, page 71) and Exercise (Chapter2, page 47) of Apostol's Introduction to Analytic Number Theory we can prove easily Lemma. If $n$ is a ...
0
votes
0answers
35 views

Primitive Root modulo n n=98

I would like to make sure I am understanding this correcting. My question is "Find primitive roots modulo $n$ using EGLF where $n=98$. I have $\phi(98)=2(7^2)=98(1-\frac{1}{2})(1-\frac{1}{7})=42$ ...
2
votes
1answer
39 views

Are there names for any of these four classes of numbers related to divisors and totatives?

Are there names for any of these four classes of numbers related to divisors and totatives? A [insert name here] of $n$ is a positive integer $\leq n$ that isn't a divisor of $n$ and that can be ...
1
vote
2answers
31 views

Is the modulus of an exponent always $\phi(n)$ in a modulo $n$ expression?

According to this proof, given an expression $$x^e\pmod n$$ the modulus of the exponent $e$ is $\phi(n)$. From Euler's Theorem, I know that $$x^{\phi(n)}\equiv 1\pmod n$$ holds true iff $x$ is ...
0
votes
1answer
22 views

Given some N, find the i for which φ(i)/i is the largest among all 2≤i≤N.

For some N, let P be the largest prime less than or equal to N, and C be some composite number less than or equal to N.If we have proved that φ(C)/C < ((P - 1) / P) then how can we say that φ(C)/C ...
0
votes
0answers
40 views

Is $\phi (k_1) + \phi (k_2)+\phi (k_3) +…\phi (k_n)=gcd(m, n) $ ? k is divisor of m and n [duplicate]

Let $k_1, k_2, k_3,\dots ,k_n$ be positive divisors of $m$ and $n$. Can you prove or disprove the following $$\varphi (k_1) + \varphi (k_2)+\varphi (k_3) +\dots+\varphi (k_n)=\gcd(m, n).$$
0
votes
0answers
28 views

How can you distinguish modular exponentiation from random?

Let $N$ be the product of two primes and let $P$ be the smallest prime larger than $N$. Let the algorithm $R(N,s)$ return $s^{1/P} \pmod{N}$. Let the algorithm $\widehat{R}(N,s)$ pick a ...
0
votes
1answer
29 views

Is the following inequality involving the sum-of-divisors and Euler totient functions true?

First Question Is the following inequality involving the sum-of-divisors $\sigma$ and Euler totient $\phi$ functions true? $$\frac{\sigma(N)}{N} \leq \frac{N}{\phi(N)}$$ Second Question When ...
1
vote
1answer
31 views

Lower Growth Rate of Euler Totient Function

Let $\phi(x)$ denote Euler's Totient function. What is the slowest growing function $f(x)$ such that $$\phi(x)=f(x)$$ occurs infinitely often for integers $x≥1$?
1
vote
1answer
28 views

Euler function and least common multiple

Could you give me hint, what is the relationship between the $\phi$ and the $lcm$ functions? In the sense, that: $p$, $q$ are primes s.t. $m < pq$ and $$ m^{lcm(p-1, q-1)+1} \equiv m \mod pq $$ ...
1
vote
0answers
29 views

Why does $\equiv 1\ (\text{mod}\ n)$ seem so important?

I'm not great with math so please feel free to correct any mistakes in my question (or add more examples). I'm a software engineer and have recently wanted to better understand the maths behind RSA ...
1
vote
1answer
35 views

Factorization of Euler totient function

We know that if $~n = p_{1}^{a_1} \cdots p_{s} ^ {a_s}~$ then $~\phi(n) = p_1^{a_1 - 1}(p_1 - 1)\cdots p_s^{a_s - 1} (p_s - 1)$. If $~q~$ is prime dividing $~\phi(n)~$ then there are two ...
0
votes
0answers
30 views

Product of first values of totient function

Let $~p~$ be prime and $~n~$ some positive integer below $~10^9$. Is there an efficient way to compute product $~ \phi(1) \cdots \phi(n) \mod p~$? It is known that $~p > \sqrt{n}~$ (i don't know if ...
0
votes
3answers
61 views

Calculate $2^{48} \equiv x \mod 140$

I've calculated the following equation and I've got this: Does there exist an easier solution?
0
votes
2answers
42 views

Euler's phi function

I have attempted a problem which required me to use Euler's phi function. In doing so I have assumed that $\varphi(xy)=\varphi(x)\varphi(y).$ Am I right to do this or have I made a mistake?
1
vote
2answers
54 views

Euler's Totient multiplication proof [duplicate]

I'm really stuck on the following question. I understand logically why this makes sense, and I've read a few proofs on this site of the multiplicative property of Euler's Totient, but those all seem ...
2
votes
0answers
222 views

Looking for help on writing a mathematical argument clearly and concisely

Let $p_n$ be the $n$th prime and $a < p_n$ be a non-negative integer . Let $f(a,p_n)$ be the number of integers $x$ such that: $$a(p_{n-1}\#) < x < (a+1)(p_{n-1}\#) \text{ and ...
1
vote
2answers
52 views

How to get the actual values from Euler's Phi function

I would like to get the list of actual values from Euler's Phi function. For example: $$\phi(12) = |1,5,7,11| = 4 $$ and I would like to get the actual list $$[1,5,7,11]$$ Of course the naive way ...
3
votes
1answer
52 views

When does $\phi (n) \mid n $?

I need to find all the integers such that $\phi (n) \mid n $, where $\phi$ is the totient function. Using $$\phi(n)=n\prod(1-1/p)$$where the product runs over all prime factors of n, one gets that ...
0
votes
0answers
27 views

When $n\mid\sum_{k=1}^{n}\phi (k)$

Consider this function. $$f(n)=\sum_{k=1}^{n}\phi (k)$$ where $\phi (k)$ is the Euler's totient function. I'm wondering are there infinitely many $n$ such that $n\mid f(n)$? For $n\leq 4000$ only ...
1
vote
1answer
36 views

if $p \equiv 3 \pmod 4$, does that automatically imply that 4 does not divide $\phi(p^k)$?

Problem: Describe all $m$ such that $\phi(m)$ is not divisible by $4$. The solution for this is this set: Let $p$ be a prime number, then $$T = \{p^k\text{ where }p \equiv 3\pmod 4\} ...
0
votes
3answers
47 views

Compute $\varphi (180)$ where $\varphi$ is the Euler totient fuction

So I was given this question. Compute $\varphi (180)$ where $\varphi$ is the Euler totient fuction. Here is my attempted solution: $\varphi (180) = ?$ $m = 180 = 2^2 \cdot 5 \cdot 9$, $p_1 = 2, p_2 ...
7
votes
1answer
104 views

Finding a $n \in \mathbb{N}$ such that $\frac{\phi(n+1)}{\phi(n)} = 4$

Let $\phi$ denote the Euler Phi Function. How do I find a $n \in \mathbb{N}$ such that $\frac{\phi(n+1)}{\phi(n)} = 4$. I can find $n \in\mathbb{N}$ such that $\frac{\phi(n+1)}{\phi(n)}=3$, for ...
0
votes
0answers
31 views

Proving a generalization of Euler's theorem

I'm working through Niven's book on Number Theory and I'm having trouble with this question: Prove that, for any integer $a$, $a^m \equiv a^{m-\phi(m)}$ (mod $m$). I can easily figure it out in the ...
2
votes
0answers
47 views

Sum of divisors and Euler phi function of a number [duplicate]

I can very well see that all prime numbers satisfies this condition. But what about other numbers, does there exist other solutions? How do I find them? Any help will be truly appreciated.
0
votes
0answers
51 views

Is it true that for every positive integer $m$ , there exist a positive integer $n$ such that $\phi(n)=m! $ ?

Is it true that for every positive integer $m$ , there exist a positive integer $n$ such that $\phi(n)=m! $ ?
2
votes
2answers
57 views

Find all $n$ such that $\varphi(n) \equiv 2 \pmod 4$ [closed]

My question is Find all $n$ such that $\varphi(n) \equiv 2 \pmod 4$, where $\varphi(n)$ is the Euler totient function. I am no where to start so any hint or help ? and if we are given such a ...
0
votes
2answers
33 views

Exponentiation of big numbers with Euler Theorem

I need to compute $5^{12241} \pmod{13}$ and as suggestion I have that I should use the Euler's theorem. The latter states that whether $a$ is relatively prime to $n$ then $a^{\phi(n)}=1\pmod{n}$. ...
0
votes
2answers
70 views

Show that $\phi(p^e)=p^e-p^{e-1}$

In an exercise I was asked to show that if $R$ is a ring with relatively prime ideals $I_1,I_2$ then $R/I \cong R/I_1 \oplus R/I_2$ where $I=I_1 \cap I_2$ and $\oplus$ is the direct sum. A follow on ...
0
votes
0answers
17 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 ...
-2
votes
1answer
50 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
34 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
17 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$. ...