Skip to main content

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
30 views

The solutions of $(2p^x)^{\varphi(2p^x)}+z^{\varphi(z)}=(2q^y)^{\varphi(2q^y)}$, being $\varphi(n)$ the Euler's totient.

The solutions of $(2p^x)^{\varphi(2p^x)}+z^{\varphi(z)}=(2q^y)^{\varphi(2q^y)}$, being $\varphi(n)$ the Euler's totient such that $p \neq q$ are primes, $v_2(z)=1$ and $\exists \ r_1,r_2 : r_1 \mid z \...
The Revolution's user avatar
1 vote
1 answer
80 views

A specific inequality involving the Euler totient function.

I am trying to digest the following inequality: $$ \prod_{p \mid e} \left( 1 + \frac{1}{p - 1}\right)\sum_{\substack{t \leq \frac{z}{e} \\ (t, e) = 1}} \frac{\mu^{2}(t)}{\phi(t)} \leq \sum_{d \leq z} \...
Galimatias's user avatar
1 vote
3 answers
85 views

Calculate the last 2 digits of the following expression [duplicate]

Find last 2 digits of the following expression with modular arithmetic. $$\LARGE 7^{7^{7^{7}}} - 7^{7^{7}} - 7^7 - 7$$ I have tried taking remainders of all terms $\mod 100$ then subtracting , ...
Aryan Malik's user avatar
0 votes
2 answers
141 views

Calculate the last $3$ digits of $2008^{2007^{2006^{\cdots^{2^{1}}}}}\\$. [duplicate]

This problem is originally from PuMAC$^{a}$ $2007$. I tried using modular arithmetic (Euler's totient function$(\phi)$) but could not solve more than this: I calculated Euler's totient functions ...
NOT ACID's user avatar
1 vote
0 answers
29 views

Fermat's Little Theorem Variation Problem [duplicate]

I've seen this type of problem circulated around on this high school math competition called Number Sense, where the aim is to solve as many problems as fast as possible and more importantly, all ...
Steven Livingston's user avatar
-2 votes
1 answer
69 views

If $\varphi(n)=2p$ then $p$ is a Sophie Germain Prime [closed]

Define $n,p\in\mathbb{N}$ with p prime. I'm struggling to show that if $\varphi(n)=2p$, then $2p+1$ is prime.
Donald fischer's user avatar
0 votes
0 answers
37 views

Solving $a^{\phi(n)/2}\equiv 1 \pmod{n}$ for an unknown $a$ in the context of Euler's Theorem

Let $\phi$ denote Euler's totient function. Then, by Euler's theorem, if gcd$(a,n)=1$, then $$a^{\phi(n)}\equiv 1 \pmod{n}. $$ Consider $(\mathbb{Z}/n\mathbb{Z})^*=G$, the multiplicative group of the ...
Ty Perkins's user avatar
1 vote
1 answer
81 views

Proving $\phi(x) = n$ for natural values of $n$ has finite solutions

Question: Prove that for any given $n \in \mathbb N$, $\phi(x) = n$ has only finitely many solutions. My attempt: Let there be infinite solutions for $$\phi(x) = n$$ so every natural number greater ...
Ayush Maurya's user avatar
3 votes
4 answers
258 views

Find the last three digits of $\large\phi({3}^{2})^{\phi({4}^{2}){}^{\phi({5}^{2})^{.^{.^{.\phi(2019{}^{2})}}}}{}^{}}$

Given any positive integer $n,$ let $\phi(n)$ be the number of positive integers less than or equal to $n$ that are relatively prime to $n.$ Find the last three digits of $\large\phi({3}^{2})^{\phi({4}...
Debrogli's user avatar
  • 338
2 votes
0 answers
69 views

A divisibility property in a sequence with exponential terms [closed]

Given the sequence $(a_n)_{n\geq 1}$ with $a_n = \frac{{2 \cdot 2^{2^{n}} + 1}}{3}$, prove that $3^n \mid a_{3^n}$ for every $n \geq 1$. I thought about using LTE 2 times for the numerator but I got ...
math.enthusiast9's user avatar
0 votes
1 answer
68 views

identity of Euler's totient function

Let $p$ be a prime and $\varphi(n)$ be Euler's totient function and $m,n$ be natural numbers. Then $\varphi(p^k)=\frac{p^{k+1}-1}{p-1}$ and $\varphi(mn)=\varphi(m)(n)$ and $\varphi(p)=p-1$.But this $$ ...
Peter Mafai's user avatar
0 votes
0 answers
108 views

What is this proof in a number theory video?

https://www.youtube.com/watch?v=zP09Dw5D8nY Here at precisely 31:00, he puts up a second claim, where $|A_d| \leq \phi(n)$where $A_d$ $=$ {$1 \leq a \leq p-1 | ord_p(a) = d$}, $d|p-1$ and $p$ is prime....
Krave37's user avatar
  • 543
3 votes
2 answers
148 views

New conjecture? $(\varphi(n))! = -1 \pmod n \iff n$ is prime (nearly the same as Wilson's) [duplicate]

$$ (n-1)! = -1 \pmod n \text{ iff } n \text{ is prime}, \text{ is Wilson's theorem,} $$ But coincidentally for now the expression passed to factorial is $n - 1$ which is (iff $n$ is prime) equal to $\...
SeekingAMathGeekGirlfriend's user avatar
1 vote
2 answers
149 views

Can $\phi(n) = \sqrt{\frac{n}{2}}$ for any natural number other than $2$?

I have seen a proof that $\phi(n) \geq \sqrt{\frac{n}{2}}$, and I was wondering if equality can happen occasionally. I used a computer program and I couldn't find any solution up to a million other ...
Arfin's user avatar
  • 1,445
0 votes
0 answers
100 views

Computing $f,g$ such that $f(n)=\sum_{d|n}d\varphi(d)$ and $g(n)=\sum_{d|n}\frac{\varphi(d)}{d}$?

Let that $n$ be a natural number and $\varphi(n)$ be the Euler totient function. Is there any formula or estimation for computing functions $f,g$ such that: $$ f(n)=\sum_{d\mid n}d\varphi(d) $$ and $$ ...
Jamal Farokhi's user avatar
0 votes
1 answer
107 views

Explaining the irregularities of the number of Goldbach pairs

I am working from a paper by Hardy and Littlewood from 1923 which attempts to construct an approximation to the number of Goldbach pairs for a given $n$. On page 32, they present a product which ...
Goldbug's user avatar
  • 1,024
0 votes
4 answers
110 views

An inequality on Euler totient function

Let n be a natural number and $\phi$ be the Euler-totient function. Can we say that $4 \phi(n) \geq n?$ When $n$ is a prime, it is obviously true. I have checked for some composite numbers also and it ...
math seeker's user avatar
1 vote
1 answer
91 views

Prove (or disprove) for any $k \ge n!$, $\phi(k) \ge \phi(n!)$

I'm trying to solve this question: $$ \text{For all } k, n \in \mathbb{N} \text{ where } k \ge n! \text{ show that:} \\~\\ \phi(k) \ge (n-1)! \\~\\ \text{Where } \phi \text{ is Euler's totient ...
Mahan Lamee's user avatar
1 vote
1 answer
35 views

My idea about the number of coprime pairs up to $N$.

Today, I wanted to write a program to count how many integer pairs $(a, b)$ that satisfy: $$1 \leq a < b \leq n, \gcd(a, b) = 1$$ My first instinct was to write a function that check every pair. ...
ducbadatchem's user avatar
3 votes
2 answers
491 views

Square of prime numbers

This conjecture is inspired by the comment of @Eric Snyder: Prime numbers which end with 03, 23, 43, 63 or 83 $n$ is a natural number $>1$, $\varphi(n)$ denotes the Euler's totient function, $P_n$ ...
Craw Craw's user avatar
3 votes
0 answers
158 views

Prime numbers which end with 03, 23, 43, 63 or 83

This is inspired from this post: Prime numbers which end with $19, 39, 59, 79$ or $99$ Here I found a new formula: $n$ is a natural number $>1$, $\varphi(n)$ denotes the Euler's totient function, $...
Craw Craw's user avatar
-1 votes
1 answer
121 views

Prime numbers which end with $59$ or $79$ [closed]

This is the weak conjecture of https://math.stackexchange.com/questions/4834936/prime-numbers-which-end-with-19-39-59-79-or-99.\ $\varphi(n)$ denotes the Euler’s totient function, $n$ denotes a ...
Craw Craw's user avatar
0 votes
0 answers
86 views

On the number of divisors of $φ(n)$

An interesting question has come up to my attention, in particular what is the number of divisors of $φ(n)$, when given a natural number $n$? Where $φ$ quite unassumingly denotes Euler's Phi function....
Vaskara_GRek_O's user avatar
0 votes
1 answer
71 views

Prove that if $e.d \equiv 1 \bmod (p-1)(q-1)$ then it’s impossible to have $e.d \equiv 1 \bmod pq$

I am studying R.S.A. cryptosystem and here is the question that came to my mind. Let’s pick $p, q$ to be two primes and $n = p * q$. From that we calculate Euler’s totient function: $$ \phi(n) = (p - ...
QuestionEverything's user avatar
0 votes
0 answers
60 views

On the cardinality of solution sets of $φ(x)=n$

It is known that given a positive integer $n$, the number of solutions of the equation $φ(x)=n$ is finite, where $φ$ denotes Euler's Phi function. So, I've made an attempt to prove this fact. Here's ...
Vaskara_GRek_O's user avatar
6 votes
1 answer
258 views

A question about prime numbers, totient function $ \phi(n) $ and sum of divisors function $ \sigma(n) $

I noticed something interesting with the totient function $ \phi(n) $ and sum of divisors function $ \sigma(n) $ when $n > 1$. It seems than : $ \sigma(4n^2-1) \equiv 0 \pmod{\phi(2n^2)}$ only if ...
Aurel-BG's user avatar
  • 141
-1 votes
1 answer
83 views

Using Euler's totient theorem to compute $11^{-1}$ mod $26$ [duplicate]

I tried to solve this modular inverse equation: $11^{-1}$ mod $26$ with Fermat's little theorem: $a^{\phi (m) - 1} * a \equiv 1$ mod $m$ and reached the following solution: $11^{\phi (26)-1} * 11 \...
Dom's user avatar
  • 9
0 votes
2 answers
48 views

Is there a formula that counts the number of positive odd integers up to a given integer N that are relatively prime to N.

This is similar to the totient function, but obviously somewhat different. I would be interested to know if formulae exist for counting the positive odd integers and the positive even integers up to a ...
Maurice's user avatar
  • 11
0 votes
0 answers
37 views

Reference request: an interpretation of Euler totient function.

Let $\phi$ be the Euler totient function. Let $A_r$ be the number of coprime pairs of positive integers $a,b$ such that $2a+b=r$, $r \ge 3$. By direct computation, I verified a few examples that $\phi(...
LJR's user avatar
  • 14.6k
6 votes
0 answers
142 views

How fast does the coprime probability converge to $6/\pi^2$?

It is known that the probability that two positive integers are coprime is $6/\pi^2$. This is an amazing result. I wanted to see experimentally how the probability converges to $6/\pi^2$, but I found ...
Martin Brandenburg's user avatar
4 votes
1 answer
76 views

Sum of inverse powers of Euler's totient.

Let $\phi$ be Euler's totient function, and consider the sum: \begin{equation} \sum_{k=1}^{\infty} \left({1\over\phi(k)}\right)^s \end{equation} For what values of $s$ does this converge/diverge? ...
user1998586's user avatar
0 votes
0 answers
30 views

What would be the eta quotient for the Weierstrass equation $x^2 = y^2$?

I am trying to find an as simple as possible example of a Weierstrass equation where the eta quotient exists and is not completely trivial. What would be the eta quotient for the Weierstrass equation ...
Mats Granvik's user avatar
  • 7,420
0 votes
0 answers
60 views

Prove that if $n$ is odd and $p \mid n$, then $\sum_{m=1,\, \gcd(m,n)=1}^{\varphi(n)} (\frac{m}{p})=0$

I have to prove this statement for my class, but I have run into an issue. When I choose $n=15$, for example, and if I choose $p=3$, I get \begin{align} \sum_{\substack{1 \leq m \leq 8 \\[1pt] \gcd(m,...
idontknow123's user avatar
1 vote
0 answers
66 views

Given $a,b \in \mathbb{N}$, is it true that $\phi(\gcd(a,b))=\gcd(\phi(a),\phi(b))$?

Let $a,b \in \mathbb{N}$ and $d=\gcd(a,b)$. Then we have that $a/d$ and $b/d$ are coprime. I am trying to see if $\phi(a)/\phi(d)$ and $\phi(b)/\phi(d)$ are also coprime ($\phi$ is the Euler totient ...
Luigi Traino's user avatar
16 votes
2 answers
484 views

$n+1$ and $n \phi (n) + 1$ are both perfect squares if and only if $n$ is a product of twin primes?

I'm trying to prove the following conjecture concerning twin primes and Euler's totient function, which I have verified for $n$ up to 1 billion. For all $n \in \mathbb{N}$, $n+1$ and $n \phi (n) + 1$ ...
JMP's user avatar
  • 497
0 votes
0 answers
48 views

Choice of public key and private key in RSA

I am trying to dig as deep as I can into the RSA algorithm and trying to wrap my head around why the public key and it’s mod inverse have to be less than $\varphi(n)$. $\varphi(n)$ is the number of ...
user993797's user avatar
4 votes
1 answer
122 views

A special case of the equation $\varphi(n+46)-\varphi(n)=46$

Let $\varphi(n)$ denote the totient function. I try to work out necessary conditions for the equation $$\varphi(n+46)-\varphi(n)=46$$ for positive integer $n$. The problem arose from the more general ...
Peter's user avatar
  • 85.1k
0 votes
0 answers
11 views

Proving $n$ divides $φ(a^n − 1)$ for any positive integer $a$ and $n$, where $a^n - 1 > 1$ [duplicate]

How will I be able to show that $n|φ(a^n − 1)$ for any positive integer $a$ and $n$, where $a^n - 1 >1$? I already have an idea that I will probably need to use cyclotomic polynomials. Will I also ...
196884 is 196883 plus 1's user avatar
2 votes
1 answer
142 views

Prove that φ(n) + d(n) ≤ n + 1 [duplicate]

Prove that φ(n) + d(n) ≤ n + 1. d(n) is the number of positive divisors of n. φ(n) is the Euler's Totient Function. Attempt: For a prime number n, φ(n) = n - 1 (all numbers less than n are relatively ...
comp.course.master's user avatar
0 votes
0 answers
63 views

m = 121, determine the possible values of $ord_m(a)$ and determine how many congruence classes mod m have each order. [duplicate]

For m = 121, determine the possible values of $ord_m(a)$ and determine how many congruence classes mod m have each order. Attempt: The number of elements coprime to 121: $\varphi(121)=110$ coprime to ...
Mzq's user avatar
  • 254
8 votes
0 answers
113 views

Is the smallest solution always a prime number?

Let $\varphi(n)$ denote the totient function and let $k$ be a positive even integer. Define $f(k)$ to be the smallest positive integer $n$ satisfying $$\varphi(n+k)-\varphi(n)=k$$ If for every even ...
Peter's user avatar
  • 85.1k
8 votes
0 answers
221 views

Does $f(46)$ exist?

Let $\varphi(n)$ denote the totient function. For an even positive integer $k$ , define $f(k)$ to be the smallest composite number $n$ satisfying $$\varphi(n+k)-\varphi(n)=k$$ if such a number $n$ ...
Peter's user avatar
  • 85.1k
1 vote
2 answers
90 views

Why is $\phi(pq) \neq pq-4$?

I currently am seeing that if $p$ and $q$ are primes, that $\phi(pq) = pq-4$ and am wondering what I am doing wrong. First, I see that if a number $d$ is greater than $1$ and divides $pq$, then it ...
Princess Mia's user avatar
  • 3,009
2 votes
1 answer
161 views

Infinitely many solutions for $\phi(n+2) = \phi(n) + 2$?

A friend of mine gave me a number theoretical problem the other day: Show that there are infinitely many solutions to this equation ($n\in \mathbb{N}$, $\phi$ is Euler's totient function): $\phi(n+2)=\...
Ismail Fayed's user avatar
0 votes
0 answers
83 views

The Euler Totient function $\varphi(n)$ approximates $\frac{6n}{\pi^2}$ on average.

Let $V_n$ equal the number of visible points on the line $x + y = n$. Given the Probability that two random numbers are coprime is $\frac{6}{\pi^2}$, we can state: \begin{equation} \mathbb{E}[V_n] \...
vengy's user avatar
  • 1,913
1 vote
0 answers
99 views

Euler Phi Function for Gaussian integers

I am considering the Euler totient function for Gaussian integers. In reference to this question, I would wish to use the fact that $\phi(p^{k})=N(p)^{k−1}\phi(p)$ if $p$ is prime, but have not ...
V. Elizabeth's user avatar
0 votes
0 answers
66 views

Equating Euler's Totient Function to the number of visible lattice points.

The function $V(a)$ checks for lattice point visibility on the line $x+y=n$ from the origin: \begin{gather} V(a) = \begin{cases} 1& \text{if }\mathrm{gcd}(a, n-a) = 1\\ 0&\text{...
vengy's user avatar
  • 1,913
1 vote
1 answer
186 views

Euler's totient function to estimate $\pi$

Euler's totient function $\varphi(n)$ to estimate $\pi$ $$\pi = \sqrt{6 \times \left( \lim_{n \to \infty} \left( \frac{1}{n} \sum_{i=1}^{n} \frac{\varphi(i)}{i} \right)^{-1} \right)}$$ The Idea ...
vengy's user avatar
  • 1,913
6 votes
1 answer
318 views

Euler's totient function and primes for even and odd numbers.

Noticed these two patterns while playing with Euler's totient function $\varphi(n)$ and primes: $$\text{For } n \text{ even}, \text{ if } \varphi(n) = \frac{n-2}{2} \text{ then } \frac{n}{2} \text{ is ...
vengy's user avatar
  • 1,913
0 votes
0 answers
33 views

Question about a proof of $\phi(r)$ incongruent integers

Hello I have a particular question, about the proof of the following theorem: Theorem: If $r|p-1$, with $p$ an odd prime, there are $\phi(r)$ incongruent integers which have order $r$ modulo $p$. ...
TreeBook1's user avatar

1
2 3 4 5
27