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
2answers
57 views

$(1^n+2^n+3^n+4^n)\mod5$ and using euler totient function to solve this

The problem gives us an integer $n$ which can be extremely large (can exceed any integer type of your programming language) and we need to calculate the value of the given expression . $$(1^n+2^n+3^n+...
2
votes
1answer
39 views

Number of distinct remainders modulo n smaller than Euler's totient function

How come that the number of distinct remainders $a_{k}$ for $g^{k}\equiv a_{k} \mod (n)$ for specific positive $n$ and any positive $g$ and $k=1,2,3...$ is never greater than $\varphi (n)$ (Euler's ...
0
votes
1answer
20 views

Arithmetic mean of the integers in set $S=\{k:k\in \mathbb{Z}, 1\leq k\leq n$ and $gcd(k,n)=1\}$

Or stated simply, what is the arithmetic mean of the totatives of $n$? From this question here I can see that the sum of the totatives is given by the formula $\large\frac{n\times\phi (n)}{2}\large$. ...
2
votes
1answer
29 views

How to count the number of perfect square greater than $N$ and less than $N^2$ that are relatively prime to $N$?

I know a little about Euler's totient function that counts integer less than $N$ that are relatively prime to $N$. But I don't know how to modify the function for perfect square numbers, or maybe ...
1
vote
1answer
36 views

Some questions on Euler's phi function

I was reading Number Theory by George E. Andrews (Dover 1994,) problem set 6-1, p. 81. (I'm not a student; I just find problems like these entertaining like some people enjoy crosswords or Sudoku.) ...
1
vote
1answer
62 views

Find all the numbers $n$ such that $\varphi(n)=5$

Find all the numbers $n$ such that $\varphi(n)=5$ Attempt: $$n=\prod\limits_{i=1}^{k} p_i^{\beta_i}$$ $$\varphi(n)=\prod\limits_{i=1}^{k}p^{\beta_i-1}(p-1)$$ We need: $$\prod\limits_{i=1}^{k}p^{\...
3
votes
3answers
95 views

Find the Prime Factorization of $\varphi(11!)$

Find the Prime Factorization of $\varphi(11!)$ What I did: $\varphi(11!)=\varphi(11)\cdot\varphi(10)...\varphi(1)$ $$\varphi(11)=2\cdot 5\\ \varphi(10)=2^2\\ \varphi(9)=3\cdot 2\\ \varphi(8)=2^2\\ ...
1
vote
0answers
49 views

Explanation about proof of formula for Euler's function

Explanation about reduced residue system theorem Theorem 3-8 from Leveque's Elementary Theorem of Numbers: $$\varphi(m)=m\prod_{p|m}(1-1/p)$$ where the notation indicates product over all ...
6
votes
2answers
63 views

Explanation about reduced residue system theorem

I need an explanation of the following theorem from Leveque's Elementary Theory of Numbers (page 44): Theorem 3-7 If $(m,n)=1$ then $\varphi(mn)=\varphi(m)\varphi(n)$ Proof: Take integers m,n ...
6
votes
2answers
137 views

Number of solutions to this nice equation $\varphi(n)+\tau(n^2)=n$

How many natural numbers $n$ satisfy the equation$$\varphi(n)+\tau(n^2)=n$$where $\varphi$ is the Euler's totient function and $\tau$ is the divisor function i.e. number of divisors of an integer. I ...
2
votes
1answer
23 views

Counting the number of integers in a reduced residue system congruent to some integer modulo a prime

Given integers $a$ and $r$ as well as an arbitrary prime $p$ with $0\leq r\leq p-1$, how many natural numbers are less then or equal to $a$ coprime to $a$ and congruent to $r$ modulo $p$. At first I ...
1
vote
1answer
46 views

Relation between $\gcd$ and Euler's totient function .

How to show that $$\gcd(a,b)=\sum_{k\mid a\text{ and }k\mid b}\varphi(k).$$ $\varphi$ is the Euler's totient function. I was trying to prove the number of homomorphisms from a cyclic group of order ...
1
vote
1answer
21 views

Prove that for any positive integer $t$, there exists a positive integer $n$ such that the base $10$ representation of $\phi(n)$ ends with $t$ zeros.

Prove that for any positive integer $t$, there exists a positive integer $n$ such that the base $10$ representation of $\phi(n)$ ends with $t$ zeros. The base $10$ representation is confusing me a ...
0
votes
1answer
33 views

A multiplicative property of the Euler totient function $\phi$ [duplicate]

How can I show that if $\gcd(a,b)=d$, then $$ \phi(ab)= {\phi(a) \phi(b) d \over\phi(d)} $$ I know I have to use the fact that $$\phi(m)= m \cdot\prod_{p|m} (1-\frac1p),$$ where the $p$ ranges ...
5
votes
0answers
29 views

Find the order of $U_{2n}$

Let $n$ be an odd integer and let $k$ be the number of elements in $U_n.$ What is the order of $U_{2n}$? I have said $\left\lvert U_{2n}\right\rvert=\varphi(2n)=\varphi(2)\varphi(n)=\varphi(n)=k.$ (...
4
votes
1answer
40 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
57 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
86 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 (5,1),(10,1),(15,...
0
votes
0answers
45 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
54 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
32 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)= \frac{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
117 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$ that ...
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: $a^{\...
0
votes
1answer
57 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
283 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 \lim_{...
1
vote
0answers
49 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(...) + u'(t)$, ...
1
vote
1answer
59 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
70 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
26 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
36 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
42 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
42 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
42 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
31 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
45 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
36 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
36 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
31 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
37 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 situations:...
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
66 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
47 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
65 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
53 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 ...