Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [totient-function]

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$.

0
votes
0answers
56 views

Can we exploit the unique totient property of primes for a solution to Goldbach's Conjecture (strong)?

The following setup takes advantage of the fact that the totient of every prime p is p-1: Use an “All or nothing” approach in that: $$4\leq 2n=p+q\quad p,q\in\mathbb{P}\iff\forall 2n\geq 4, 2n=r+t\...
0
votes
3answers
61 views

remainder of $(2^{87}-1) \div 89$

What will be the remainder when $2^{87} -1$ is divided by $89$? I tried it solving by Euler's remainder theorem by separating terms: $$ \frac {2^{87}}{89} - \frac{1}{89}$$ $\phi (89) =88 $ ...
3
votes
0answers
43 views

Is the function $\ g(n)\ $ defined for every positive integer $\ n\ $?

Define $$f(m):=m\mod \varphi(m)$$ where $\ \varphi(m)\ $ denotes the totient function. Now define $\ g(n)\ $ to be the smalles positive integer $\ m\ $ with $\ f(m)=n\ $ , if such a positive integer ...
1
vote
1answer
48 views

Show that m has to be even if for every integer $a$, $a^m\equiv1\pmod{n}$.

Let $n$ be a positive integer, and let $m$ be an integer such that $a^m\equiv1\pmod{n}$ for every integer $a\ \epsilon\ (\mathbb Z/n\mathbb Z)^*$. Show that $m$ is even. I know that $a^{\phi(n)}\...
0
votes
1answer
16 views

Modular exponentiation with the Carmichael function

This is something I have been thinking of using in a math competition against other players so it would be very helpful to me if it was explained. How would someone reduce a problem such as $\frac{7^{...
0
votes
0answers
22 views

Totient summatory function and other function yields how many perfect squares?

How many perfect squares does the totient summatory function yield? $$ \Phi(n)=\sum_{k=1}^{n}\phi(k). $$ How many perfect squares does this function yield? $$ \Lambda(n)= \sum_{k=1}^{n} \phi(k)\phi(...
0
votes
0answers
45 views

number of coprimes to a less than b

We know that number of coprimes less than a number can be found using euler function https://brilliant.org/wiki/eulers-totient-function/ But if there are two numbers p,q and we need to find number of ...
7
votes
4answers
543 views

Find last 3 digits of $ 2032^{2031^{2030^{\dots^{2^{1}}}}}$

Find the last 3 digits of this number $$ 2032^{2031^{2030^{\dots^{2^{1}}}}} $$ So obviously we are looking for $x$ so that $$ 2032^{2031^{2030^{\dots^{2^{1}}}}} \equiv x \quad \text{mod}\hspace{0.1cm} ...
2
votes
2answers
67 views

Count Integers Not Greater Than $a$ Coprime To $b$ [on hold]

I'd like to ask how to count $f(a,b)$, the number of integers not greater than $a$ which are coprime to a given number $b$. Can $f$ be expressed using Euler's totient function?
0
votes
2answers
41 views

Another sum involving totient function or gcd

Motivated by this question, My question pertains to closed form of the sum $$\sum_{d|n}\frac{\phi(d)}{d}$$ There are some formulae and expressions for $\sum_{n}\frac{\phi(n)}{n}$, but what about when ...
0
votes
1answer
32 views

How can I break up a larger number into smaller numbers and exponents?

I'm trying to compute the Euler's totient function for large numbers where I can't use the other rules in order to solve for the totient. For example: $\theta(600) = (2^3 * 3 * 5^2)$ I am confused ...
2
votes
6answers
96 views

Computing last two digits of $27^{2018}$

For abstract algebra I have to find the last two digits of $27^{2018}$, without the use of a calculator, and as a hint it says you should work in $\mathbb{Z}/100\mathbb{Z}$. I thought breaking up ...
0
votes
3answers
45 views

How to calculate $\varphi(103)$?

How to calculate $\varphi(103)$? I know the answer is $102$ by looking at Wiki. But how can I find the multiplication of the prime numbers in order to use Euler's formula?
0
votes
1answer
43 views

Sum of the number of relatively prime integers up to $x$, $x-1$, $\ldots$, $1$

If there is a number $x$, and we want to find the sum of the number of relatively prime integers up to $x$, $x-1$, $\dots$ until $1$, is there a formula for this or any way to solve it? Like if the ...
2
votes
1answer
49 views

Find the remainder when $(34! + {75}^{37})^{39}$ is divided by $37$

Since Fermat Theorem is $a^{36} \equiv 1 \mod {37}$, ${75}^{37}$ becomes ${75}^{36} \times 75$ and in $\!\!\mod {37}$ they both become $1$. I have $(34! + 1)^{39}$. I do the same again with $(34! + ...
0
votes
0answers
62 views

Show that for $n_1,n_2,…,n_p$ natural numbers, there is a natural number $n$ such that $\varphi(n)=n_1!n_2!…n_p!$

Show that for $n_1,n_2,...,n_p$ natural numbers, there is a natural number $n$ such that $\varphi(n)=n_1!n_2!...n_p!$. In the proof, they order the numbers such that $n_1\leq n_2 ...\leq n_p$. Let $...
0
votes
1answer
46 views

What happens to $n^{\phi(p)} \equiv 1$ when $n$ and $p$ are not co-prime?

We know $n^{\phi(p)} \equiv 1$ in the case $n$ and $p$ are co-prime i.e. $ gcd(n,p) = 1$. What is the case when they are not co-prime? What happens to $n^{\phi(p)} \equiv 1$?
0
votes
3answers
49 views

How do I prove that $\mathbb{Z}_n^*$ is a group? [closed]

$\mathbb{Z}_{n}^{*}=\left \{ a\Big|\gcd\left (a,n \right )=1 \right \}$ Now, my problem is that: If $a_1,a_2\in \mathbb{Z}_{n}^{*}$, how do I prove that $a_1\cdot a_2\in \mathbb{Z}_{n}^{*}$? Can you ...
1
vote
1answer
60 views

Use Euler's Theorem to reduce the power factor $P$ to a value $R$ less than $\phi(m).$

I need to calculate $12345^P \pmod m$, where $P=3^{124}+2$ and $m=53892647$. The only thing that is confusing me is that to reduce it using Euler's theorem $m$ needs to be square-free number however $...
4
votes
2answers
65 views

Euler's totient $\phi$ function as a product of primes

Many web pages say that Euler's totient function $\phi(n)$ can be given as $$\phi(n)=n \prod_{p|n} \biggl(1- \frac{1}{p} \biggr)$$ But $\phi(1)=1$, and no primes divide $1$. Surely this gives $$\...
1
vote
1answer
38 views

. Suppose gcd(a, m) = d and that m > 1. Consider the congruence ax ≡ b (mod m). Should there be a solution for every choice of b?

If yes, prove your claim; if not, give a counter example X is not told so I assume it can be any orbitrary number. b is also abitrary, with that being said, isn't true due to those 2 factors?
3
votes
2answers
75 views

Can the smallest solution of $\varphi(k)=n$ be an even positive integer?

Suppose, $n$ is a positive integer and the equation $$\varphi(k)=n$$ has a solution. Upto $n=20\ 000$, the smallest solution $k$ (if existent) is an odd positive integer. Do positive integers $n$ ...
0
votes
1answer
99 views

Fermat's Little Theorem & Euler's Theorem

Make a table showing the values of $a, a^2, a^3, a^4, a^7, (a^3)^7$ modulo 33 for 0 ≤ a ≤ 16, expressing the entries as integers in the interval [−16, 16]. Explain why two of the columns are the same. ...
2
votes
1answer
36 views

Euler's totient function?

I've got a few questions to ask regarding Euler's totient function and modular arithmetic: Find $\varphi(24)$. What will the indication of a 24-hour clock be $7^{19}$ hours after 1 : 00? I've worked ...
2
votes
1answer
52 views

Factorization of large (60-digit) number

For my cryptography course, in context of RSA encryption, I was given a number $$N=189620700613125325959116839007395234454467716598457179234021$$ To calculate a private exponent in the encryption ...
2
votes
4answers
78 views

Show that $n^{13} - n$ is divisible by 2, 3, 5, 7, 13 [duplicate]

Show that $n^{13} - n$ is divisible by $2, 3, 5, 7$ and $13$ I know this has been asked before, but the other approaches seem different than mine. Here is my approach: Look at $ n^{13} -n \equiv 0 ...
1
vote
0answers
57 views

Is this a valid proof of Euler's product formula for the totient function?

I will attempt the proof using induction. But first, a lemma: Lemma 1: If $ n = p^{\alpha} $, where $ p $ is prime and $ \alpha\in\mathbb{N} $, then $ \phi(n) = n(1-\frac{1}{p}) $. $ \underline{...
0
votes
0answers
33 views

Show $\frac{\sum_{n=1}^{\infty}\frac{1}{\phi(n)^s}}{\zeta(s)}=\prod_{p}(1-1/p^s+1/(p-1)^s)$.

I want to show that the following equality and that the product is absolutely convergent and uniformally convergent on compact subsets of ${s:Re(s)>1}$. $$\frac{\sum_{n=1}^{\infty}\frac{1}{\phi(n)^...
2
votes
2answers
74 views

Find at least $5$ integers $n$ such that $\varphi(n)=16$

Let $\varphi(n)$ denote Euler's totient function. Find all integers such that $\varphi(n)=16$. Answers given were $17,32,34,40,48.$ I am thinking a generalisation of this problem: is there a way ...
0
votes
1answer
36 views

Regarding square-free integers and Euler's function [closed]

Let $\phi$ be Euler's totient function. Prove that if $\text{gcd}(\phi(n), n) = 1$, then $n$ is a square free integer.
5
votes
1answer
241 views

Euler's Totient Function and Residue Classes

I have been working on a formula that seems to be a generalization of Euler's Totient Function and have a number of questions: I have been researching online and can't seem to find this function ...
0
votes
1answer
33 views

Question about conservation( unchangingness ) of order of modular multiplicative cycle when cycle is multiplied by relatively prime number.

I'm currently trying to learn about totient, while following the proof of the fermat's little theorem I got stuck at some part and that part include a question of title. first, to prevent the confuse ...
3
votes
0answers
37 views

Lower bounds for totient function of a Carmichael number

Short version: I am wondering if there are any good bounds of the form $\phi(n) \geq f(n)\cdot n$ with $f(n)$ close to 1 for high $n$, optionally under the assumption that $n$ is a Carmichael number. ...
6
votes
1answer
110 views

Asymptotic formula for $\sum_{k=1}^n \frac{1}{\varphi(k)}$?

Is an asymptotic formula of $$\sum_{k=1}^n \frac{1}{\varphi(k)}$$ known ? The infinite sum $$\sum_{k=1}^\infty \frac{1}{\varphi(k)}$$ diverges which can be shown by comparing it to the harmonic ...
1
vote
0answers
59 views

Are these limits correct? $\lim_{n\to \infty}\text{sup} \frac{\lambda (n)}{n}=1$ and $\lim_{n\to \infty}\text{inf} \frac{\lambda (n)}{n}=0$ exist?

I learned that from here for Euler totient function $\phi (n)$ , we have $$\lim_{n\to \infty}\text{sup} \frac{\phi (n)}{n}=1$$ $$\lim_{n\to \infty}\text{inf} \frac{\phi (n)}{n}=0$$ However, ...
0
votes
2answers
63 views

How do I find the last digit of a large exponent?

I am trying to find the last digit of $2^{214412412}$ using Euler's theorem. I forgot how to do this using modular arithmetic. Please, can someone explain this to me?
4
votes
0answers
70 views

For which even integers $k$ has $\varphi(n+1)-\varphi(n)=k$ a solution?

For which even integers $k$ does the equation $$\varphi(n+1)-\varphi(n)=k$$ have a solution ? $\varphi(n)$ denotes the totient function and $n$ is a positive integer. For the following $|k|\le 1\ ...
11
votes
1answer
123 views

Is the function $f(n)=\varphi(n)+\varphi(n+1)-n$ surjective?

For every positive integer $n$ define $$f(n)=\varphi(n)+\varphi(n+1)-n$$ $\varphi(n)$ denotes the totient-function. Is $f(n)$ surjective on the non-negative integers ? The first non-negative ...
0
votes
2answers
63 views

Is the multiplicative group $\Bbb Z_{36}^\times$ cyclic?

I'm trying to answer this question but also understanding a smart method to find if a group like the one mentioned has a cyclic generator or not. I know that similar questions have already been asked ...
2
votes
2answers
82 views

Which of these numbers could be the exact number of elements of order $21$ in a group?

I'm reading "Contemporary Abstract Algebra," by Gallian. This is Exercise 4.46. Which of the following numbers could be the exact number of elements of order $21$ in a group: $21600, 21602, 21604$?...
0
votes
1answer
33 views

Direct passage from $n$ prime to $n$ non-prime in Euler Totient Function $\Phi$

I wish to derive, for a proof, the Euler Totient Function starting from the case $n$ prime to $n$ non-prime. Let $n$ prime, we know $\Phi(n)=n-1$. But what if now I assume $n=p_0^{a_0}p_1^{a_1}...p_r^...
2
votes
1answer
83 views

Expression for the inverse of Euler's totient function $\phi^{-1}$

I have to demonstrate that $$\phi^{-1}(n)= \prod_{p|n}(1-p)$$ where $\phi(n)$ is the Euler's totient function. I know that I can write $\phi$ in terms of the Mobius function $\mu$ as$$\phi(n)= \sum_{...
1
vote
1answer
30 views

A question concerning higher residues (quadratic and so on)

When $x \equiv a \pmod{n}$ one says that $a$ is the residue of $x$ modulo $n$. So one can define: $a$ is a 1-residue modulo $n$ if there is an $x$ with $x \equiv a \pmod{n}$. Clearly, every $a&...
7
votes
1answer
79 views

On numbers with small $\varphi(n)/n$

Let $\Phi(n) = \varphi(n)/n = \prod_{p|n}(p-1)/p$ be the "normalized totient" of $n$. Some facts: $\Phi(p) = (p-1)/p < 1$ for prime numbers with $\lim_{p\rightarrow \infty}\Phi(p) = 1$ $\Phi(n) = ...
8
votes
0answers
116 views

Odd numbers with $\varphi(n)/n < 1/2$

The topic was also discussed in this MathOverflow question. From $\varphi(n)/n = \prod_{p|n}(1-1/p)$ (Euler's product formula) one concludes that even numbers $n$ must have $\varphi(n)/n \leq 1/2$ ...
0
votes
1answer
25 views

Find the number of elements in set $A=\{1,2,\ldots, N\}$ such that the element has multiples in each row of a $N \times N$ square matrix.

For a given $N$, the $N \times N$ grid looks like : $1$ $\qquad$ $N+1$ $\qquad$ $2N+1$ $\qquad$ $3N+1$ $\qquad$...$\qquad$ $N(N-1)+1$ $2$ $\qquad$ $N+2$ $\qquad$ $2N+2$ $\qquad$ $3N+2$ $\qquad$... $...
0
votes
1answer
14 views

Looking for the name and properties of ${\varphi}_{2} (r, N) = \sum_{- N \le s, t \le N, (r, s, t) = 1} 1$ and $\sum_{d \mid r} \mu (d)/d^2$

I am counting the number of unique polynomial candidates for a fixed $r$ where $1 \le r \le N$ with $|s|, |t| \le N$ for naive height $N \ge r$. This sum is $${T}_{2} \left({r, N}\right) = \sum_{\...
1
vote
3answers
86 views

find the smallest $N$ that $\varphi(n)\ge5$ for every $n\ge N$

I know that the solution is with Euler function. I could not understand how to show this. thanks.
0
votes
1answer
47 views

Is there a canonical extension of Euler's totient function to the reals?

Assumption: if a set $X\times Y$, exists such that $\forall\textbf{u},\textbf{v}\in X\times Y. \left(u_1=v_1\implies u_2=v_2\right)$, then a function $f$ exists such that $f:X\to Y$. The set of ...
1
vote
1answer
68 views

Is it possible to evaluate the summation $x=\sum_{n=1}^\infty \frac{\phi(n)}{n^2}$?

$$x=\sum_{n=1}^\infty \frac{\phi(n)}{n^a},\quad\text{where $\phi$ is the Euler-phi/totient function and $a\geq1$}$$ Can this even be evaluated? It clearly converges for all $a>2$, since the ...