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
-5 votes
1 answer
67 views

If $a$ and $n$ are natural coprime and $a^{n-1}\equiv\bmod(n)$ so $n$ is prime? [closed]

If $a$ and $n$ are natural coprime and $a^{n - 1}\equiv 1 \bmod(n)$ so $n$ is prime?
David's user avatar
  • 9
0 votes
0 answers
105 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
  • 414
3 votes
2 answers
132 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 $\...
Daniel Donnelly's user avatar
-3 votes
0 answers
32 views

How many n-element k-complex seeds [duplicate]

Let's say a seed is a permutation of every integer from 1 to n For example all seeds of n = 3 are: (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1). Let's say a permutation function does ...
Bartek_0x00's user avatar
1 vote
2 answers
135 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 ...
Aria's user avatar
  • 1,435
0 votes
0 answers
94 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
94 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
80 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
77 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
26 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. ...
Minh Đức Hoàng's user avatar
3 votes
2 answers
464 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$ ...
Rédoane Daoudi's user avatar
3 votes
0 answers
153 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, $...
Rédoane Daoudi's user avatar
-1 votes
1 answer
115 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 ...
Rédoane Daoudi's user avatar
0 votes
0 answers
75 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
61 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
55 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
0 answers
200 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
  • 121
-1 votes
1 answer
81 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
45 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.5k
5 votes
0 answers
136 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
64 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
27 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,366
0 votes
0 answers
57 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
57 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
471 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
  • 487
0 votes
0 answers
46 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
116 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
  • 83.7k
0 votes
0 answers
9 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 ...
L Z's user avatar
  • 59
2 votes
1 answer
105 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
  • 252
8 votes
0 answers
109 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
  • 83.7k
8 votes
0 answers
217 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
  • 83.7k
1 vote
2 answers
89 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
  • 2,321
2 votes
1 answer
144 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
70 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,903
1 vote
0 answers
77 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
59 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,903
1 vote
1 answer
177 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,903
6 votes
1 answer
299 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,903
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
4 votes
0 answers
207 views

Question about the proof of $\phi(a \cdot b) = \phi(a)\phi(b)$

Hello I have a question about the following theorem proof. There I am particularly interested in the part that I have highlighted in thick. Theorem: If $a$ and $b$ are two mutually prime integers, $\...
TreeBook1's user avatar
-1 votes
1 answer
66 views

Modular Congruences with Raised Powers [duplicate]

I have a question regarding modular arithmetic rules. I need to find a $k$ such that $$4^{k}=1 \bmod\ 103$$ By Euler's Theorem $a^{\phi (n)} \equiv 1 \bmod n$ if $a$ and $n$ are relatively prime. Thus ...
Riccardo Caiulo's user avatar
2 votes
0 answers
48 views

Finding orbit in a group action of automorphism group of dihedral group on the dihedral group.

Finding orbit in a group action of automorphism group of dihedral group on the dihedral group. Let $$D_{2n}=\langle a,b:a^n=b^2=1,bab^{-1}=a^{-1}\rangle $$ be the dihedral group of order $2n$ and $...
idiot's user avatar
  • 117
3 votes
1 answer
94 views

Euler's Totient Function - Multiplicativity via Group of Units

The ring $\mathbb{Z}_{n m}$ is isomorphic to the ring $\mathbb{Z}_n \times \mathbb{Z}_m$ if $\operatorname{gcd}(m, n)=1$ holds. Let us prove the property that the Totient Function $\varphi$ is ...
calculatormathematical's user avatar
0 votes
0 answers
48 views

Bounds on a prime exponent problem

In an IMO SL problem for 2020 number theory problem 6, there is a part of the solution which I do not get which states the following: Let $m>5$ be large positive integer and also let $n=p_1p_2......
Aurora Borealis's user avatar
1 vote
0 answers
162 views

Modular tetration (power tower) for non-coprime numbers case

I'm writing algorithm for calculating $a^{a^{...^{a}}}$ mod $m$. According to Euler's theorem, $a^k = a^{k\mod{\phi(m)}}$ mod $m$, if $a$ and $m$ are relatively primes. If $m = \prod_{i=0}^n p_i^{\...
Vitaliy Volovyk's user avatar
0 votes
0 answers
61 views

Problem on the totient function and the divisor function

I stumbled upon a problem in my number theory class regarding the divisor function $d(n)$ and the totient function $\phi(n)$, where the problem states: Does there exist a constant $C$ such that $\frac{...
Aurora Borealis's user avatar
1 vote
1 answer
79 views

Proving a natural odd number n is prime based on constraints on order of numbers mod n

Let n be an odd natural (positive) number such that $3 \nmid n$. It is further given that: $3^{\frac{n-1}{2}} \equiv -1 \pmod{n}$ The order of 9 modulo n is $\frac{n-1}{2}$ Prove that n must be ...
giorgio's user avatar
  • 319
0 votes
3 answers
106 views

Proving $\sigma_1(n) \phi(n)>n/2$ [closed]

I need to prove that $\sigma_1(n) \phi(n)$ is less or equal than $n^2$ and greater than $n/2$. I managed to prove the first part but now I need some help on proving that it's greater than $n/2$. I got ...
mhighwood's user avatar
  • 143

1
2 3 4 5
26