2015 solutions for quotient function!

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

raxu

398 posts

raxu

#1 h Jun 26, 2015, 1:45 AM • 7 Y

Y by rightways, navi_09220114, tenplusten, megarnie, Adventure10, Mango247, rudransh61

Let $\varphi(n)$ denote the number of positive integers less than $n$ that are relatively prime to $n$ . Prove that there exists a positive integer $m$ for which the equation $\varphi(n)=m$ has at least $2015$ solutions in $n$ .

Proposed by Iurie Boreico

This post has been edited 2 times. Last edited by v_Enhance, Aug 23, 2016, 12:47 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

FlakeLCR

1791 posts

FlakeLCR

#3 h Jun 26, 2015, 2:29 AM • 7 Y

Y by jh235, Cindy.tw, L567, yayitsme, Tang_Tang, Adventure10, Mango247

By the Prime Number Theorem, which states $\pi(x)\approx\frac{x}{\ln x}$ , we can take the approximation $\pi(2x)-\pi(x)\approx \frac{2x}{\ln 2x}-\frac{x}{\ln x}=\frac{2x-x\left(1+\frac{\ln2}{\ln x}\right)}{\ln 2x}$ , which can be made as close to $\frac{x}{\ln 2x}$ as we like, which can be made far greater than 2015 (If you want to be rigorous, you can use several well known bounds on $\pi(x)$ .) Pick an arbitrary large composite $x$ (to avoid boundary cases) that satisfies $\pi(2x)-\pi(x)>2015$ .

It is clear that for any $n<2x$ , $n$ has at most $1+\log_2 x$ prime factors (the maximal case is when $n$ is a power of 2, of course). Let $q=\lceil 1+\log_2 x\rceil$ .

Now, let $S$ be the set of primes less than $x$ . Consider the numbers $m=\prod_{p\in S} p^q(p-1)$ , and $k=\prod_{p\in S} p^{q+1}$ . It is clear $\varphi(k)=m$ , and $n<x\implies n|k$ . Now, for any prime $p\in (x,2x)$ , consider the number $\frac{pk}{p-1}$ . It is obvious that $p-1|k$ , as otherwise there must exist a prime divisor of $p-1$ above $x$ , but $p-1<2x$ , and $2|p-1$ , so this is absurd. Therefore $\frac{pk}{p-1}$ is an integer, and it is easy to verify that $\varphi\left(\frac{pk}{p-1}\right)=(p-1)\prod_{r\in S} r^{q-\nu_r(p-1)}(r-1)=(p-1)\frac{m}{p-1}=m$ .

This works for any $p\in(x,2x)$ , which there are over 2015 of, thus we have found over 2015 solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

tastymath75025

3223 posts

tastymath75025

#4 h Jun 26, 2015, 3:54 AM • 3 Y

Y by bpinyourarea, Adventure10, Mango247

hmm here's the solution I foudn during the test

Lemma: For a prime $p$ , we have $\phi (p(p-1)) = \phi ((p-1)^2)$

Proof: Since phi is multiplicative, this is trivial.

Lemma 2: Let $S = [a_1,a_2,..a_n]$ be a set and let $S' = [b_1,b_2,..b_m]$ be a set. Suppose $\phi (a_1) = \phi (a_2) = .. = \phi (a_n)$ and $\phi (b_1) = \phi (b_2) = ... = \phi (b_m)$ . Furthermore, suppose that for any $i, j$ , if $d | \gcd (a_i, b_j)$ , then $d$ divides all the $a$ s and all the $b$ s. Then $\phi (a_ib_j)$ is fixed for all $i,j$ . This basically says we take the "product" of two sets, the phi's are still equal.

Proof: Let $P$ be the set of all distinct prime divisors of $\gcd(a_i, b_j)$ and use the fact that $\phi$ is multiplicative over and over again. Basically we want to show $\phi (a_xb_y) = \phi(a_wb_z)$ but then write $\phi(a_x b_y) = \phi ( \prod_{p \in P} p^{v_p (a_xb_y)} ) \phi(quotient)$ and then use algebra.

Now, we induct. Let $p_1 = 7$ and for any $i$ , take $A_i = [(p_i -1)^2, p_i (p_i -1)]$ , and define $A_1 = S_1$ . Define $S_i$ to consist of the productts of all numbers in $S_{i-1}$ with all numbers in $A_i$ . Define the $p_i$ 's so that $\gcd ( p_i-1 , (p_1-1)(p_2-1)..(p_{i-1}-1) ) = 1$ for all $i>1$ (this is easy with Dirichlet + CRT). Then by lemma 2, we can basically let $i>11$ to get $|S_i| > 2015$ and we have over 2015 numbers with the same phi value.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

-.-

27 posts

-.-

#5 h Jun 26, 2015, 5:07 PM • 3 Y

Y by jh235, Adventure10, Mango247

By the Generalized Prime Number theorem, the number of integers $n < x$ such that $n$ has at most $N$ distinct prime divisors is $\frac{x(\log\log x)^{N - 1}}{(N-1)!\log x}(1 + o_N(1))$ , which for a fixed $N$ is $o(x)$ . Pick $N = 11$ ; then there exists an $x$ such that less than $0.001x$ integers less than $x$ have at most 11 prime factors. At least $0.999x$ integers $n < x$ have at least 12 distinct prime factors, and in this case, $2^{11}\vert \phi(n)$ and $\phi(n) < x$ , so $\phi(n)$ can take on at most $\frac{x}{2048}$ different values. Thus some value $m$ is taken on at least $\frac{0.999x}{x/2048} > 2015$ times.

This post has been edited 1 time. Last edited by -.-, Jun 26, 2015, 5:07 PM
Reason: forgot a word - distinct

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

toto1234567890

889 posts

toto1234567890

#6 h Jun 27, 2015, 10:01 AM • 2 Y

Y by Adventure10, Mango247

Does there exist $m$ that there is exactly 2015 ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6874 posts

v_Enhance

#7 h Jun 27, 2015, 3:05 PM • 17 Y

Y by Darn, Mediocrity, anantmudgal09, TheOneYouWant, navi_09220114, smy2012, acegikmoqsuwy2000, Supercali, Aryan-23, Smkh, pavel kozlov, megarnie, HamstPan38825, CyclicISLscelesTrapezoid, Adventure10, Kingsbane2139, lksb

I consider the following ELEVEN PRIME NUMBERS: $S = \left\{ 11, 13, 17, 19, 29, 31, 37, 41, 43, 61, 71 \right\}$ . It has the property that for any $p \in S$ , all prime factors of $p-1$ are one digit.

Let $N = (210)^{\text{billion}}$ , and consider $M = \phi\left( N \right)$ . For any subset $T \subset S$ , we have $M = \phi\left( \frac{N}{\prod_{p\in T} (p-1)} \prod_{p \in T} p \right).$ Since $2^{\left\lvert T \right\rvert} > 2015$ we're done. $\blacksquare$

This solution was motivated by the DEEP FACT that
$(2^2-2)(3^2-3) = (7-1)(2-1)(3-1) \implies \phi(2^2\cdot3^2) = \phi(2\cdot3\cdot7).$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MathPanda1

1135 posts

MathPanda1

#8 h Jun 28, 2015, 12:30 AM • 2 Y

Y by Adventure10, Mango247

LOL this is actually a theorem: https://en.wikipedia.org/wiki/Euler's_totient_function

Conclusion/Trend: #5's are theorems (same with IMO #5 and USAMO #5).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

yugrey

2326 posts

yugrey

#9 h Jun 28, 2015, 5:42 AM • 2 Y

Y by Adventure10, Mango247

Ford's theorem is in fact much stronger.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

toto1234567890

889 posts

toto1234567890

#10 h Jun 28, 2015, 8:55 AM • 2 Y

Y by Adventure10, Mango247

Excuse me, but can you tell me what is Ford's theorem??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EulerMacaroni

851 posts

EulerMacaroni

#11 h Jun 28, 2015, 4:25 PM • 2 Y

Y by Adventure10, Mango247

toto1234567890 wrote:

Excuse me, but can you tell me what is Ford's theorem??

It's in the linked Wikipedia article...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jh235

910 posts

jh235

#12 h Aug 23, 2015, 4:15 PM • 5 Y

Y by rkm0959, Gibby, Lam.DL.01, Adventure10, Mango247

I don't know if this is of interest to anyone, but I did a little research of the topic and here is what I found. Erdos proved that if we let $N(x)$ denote the number of integers $\le x$ that can be represented (not counting multiplicity) as the Euler Totient function of some other integer, then $N(x)=o\left(x(\log x)^{\varepsilon-1}\right),$ for any $\varepsilon>0.$ Now, if we let $N'(x)$ denote the same function, but counting multiplicity then $N'(x)=\dfrac{\zeta(2)\zeta(3)}{\zeta(6)}x+O\left(\dfrac{x}{(\log x)^{\varepsilon}}\right),$ for any $\varepsilon>0.$ (Proving $N'(x)>>x$ would be more than sufficient for our needs though.) In particular, if this problem where not true, then we would get $N'(x)<2015N(x)$ which would lead to contradiction.

I just wanted to point this out, since this is an analytic approach but an approach that I think is much easier than Ford's Theorem mentioned in this thread.

This post has been edited 2 times. Last edited by jh235, Aug 23, 2015, 5:40 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

FabrizioFelen

241 posts

FabrizioFelen

#13 h Oct 24, 2015, 2:06 AM • 5 Y

Y by acegikmoqsuwy2000, Pluto1708, pavel kozlov, Adventure10, Mango247

My solution:
We define the following sets:
$C_1=\{15,16,20,24,30\}$ if $x\in C_1$ $\Longrightarrow$ $\varphi(x)=8$
$C_2=\{11.37,13.31\}$ if $x\in C_2$ $\Longrightarrow$ $\varphi(x)=360$
$C_3=\{19.97,17.109\}$ if $x\in C_3$ $\Longrightarrow$ $\varphi(x)=18.108$
$C_4=\{23.127,43.67\}$ if $x\in C_4$ $\Longrightarrow$ $\varphi(x)=66.42$
$C_5=\{29.101,71.41\}$ if $x\in C_5$ $\Longrightarrow$ $\varphi(x)=28.100$
$C_6=\{7.461,61.47\}$ if $x\in C_6$ $\Longrightarrow$ $\varphi(x)=46.60$
$C_7=\{307.53,157.103\}$ if $x\in C_7$ $\Longrightarrow$ $\varphi(x)=102.156$
$C_8=\{139.661,277.331\}$ if $x\in C_8$ $\Longrightarrow$ $\varphi(x)=276.330$
$C_9=\{199.541,397.271\}$ if $x\in C_9$ $\Longrightarrow$ $\varphi(x)=270.396$
$C_{10}=\{211.457,421.229\}$ if $x\in C_{10}$ $\Longrightarrow$ $\varphi(x)=210.456$
Let $x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x_{10}$ intergers positive such that $x_i\in C_i$ for all $1\leq i\leq 10$ the we get:
$\varphi(x_1.x_2.x_3.x_4.x_5.x_6.x_7.x_8.x_9.x_{10})=\varphi(x_1).\varphi(x_2).\varphi(x_3).\varphi(x_4).\varphi(x_5).\varphi(x_6).\varphi(x_7). \varphi(x_8).\varphi(x_9).\varphi(x_{10})$
$\varphi(x_1).\varphi(x_2).\varphi(x_3).\varphi(x_4).\varphi(x_5).\varphi(x_6).\varphi(x_7). \varphi(x_8).\varphi(x_9).\varphi(x_{10})=8.360.1944.2772.2800.2760.15912.91080.106920.95760$
$\Longrightarrow$ $\varphi(x_1.x_2.x_3.x_4.x_5.x_6.x_7.x_8.x_9.x_{10})$ is constant $\Longrightarrow$ the number of ways of choosing $x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x_{10}$ is: $5.2.2.2.2.2.2.2.2.2=2560\geq 2015$
$\Longrightarrow$ $\varphi(x)=8.360.1944.2772.2800.2760.15912.91080.106920.95760$ has at least $2015$ solutions in $x$ ...

This post has been edited 2 times. Last edited by FabrizioFelen, Feb 1, 2016, 2:13 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aiscrim

409 posts

Aiscrim

#17 h Feb 10, 2016, 10:18 AM • 2 Y

Y by Adventure10, Mango247

Over-complicated(?) solution
Note and motivation

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CsOH

13 posts

CsOH

#20 h Feb 19, 2017, 6:07 AM • 3 Y

Y by pavel kozlov, Adventure10, Mango247

I think there's an easier solution for this problem. Let $m=2^{N_1}\cdot3^{N_2}\cdot5^{N_3}$ where $N_1,N_2,N_3$ are integers large enough. Let $S=\{7,11,13,17,19,31,37,41,61,101,109,163,251,257,65537\}$ be a set of primes. Noted that for every $p\in S$ , $p-1$ only have prime factors in $\{2,3,5\}$ and $\phi(3)=2,\phi(5)=2^2$ . Therefore $m$ can be written as $\phi (2^k\cdot3^l\cdot5^m\cdot \prod_{p_i \in S} {p_i}^{x_i})$ , herein $x_i\in \{0,1\}$ . Then there are at least $2^{|S|}>2015$ solutions in $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smy2012

688 posts

smy2012

#21 h Feb 19, 2017, 8:29 AM • 1 Y

Y by Adventure10

Actually I've found a solution which is basically the same as Evan Chen's idea.
That is, to find a set $P$ comprising of prime numbers such that
$\forall p,q\in P, q\nmid \varphi(p)=p-1$
We can then get $2^{|P|}$ solutions.

We can use Dirichlet's theorem to construct such $P$ , so $|P|$ can be arbitrarily large

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blackbluecar

302 posts

blackbluecar

#43 h May 22, 2021, 3:52 AM

Y by

Interesting!

Clearly, $\varphi(p(p-1))= \varphi((p-1)^2)$ . Clearly, by induction, Dirichlet, and CRT we can construct a set of primes $P = \{p_1,p_2,...,p_{\text{big }} \}$ where $p_i-1$ is not divisible by any element in $P$ . For any $i$ , we can either choose $p_i(p_i-1)$ or $(p_i-1)^2$ and each is independent since they are relatively prime. Clearly, $2^{\text{big}} \geq 2015$ . So we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sprites

478 posts

Sprites

#44 h Aug 20, 2021, 5:52 AM

Y by

Let $p_1,p_2,p_3,......$ be an increasing sequence of primes and fix a positive integer $k$
Clearly $N=p_1 p_2 p_3.....p_k$ and $x_i=N \cdot (1 - \frac{1}{p_i})$ satisfies $\phi(N)=\phi(x_i)$ since $\frac{\phi(x_i)}{x_i}$ $=\prod(1-\frac{q}{p_j}) \cdot \frac{p_i}{p_i-1}$ $=$ ${\phi(N) \over N }\cdot$ $\frac{p_i}{p_i-1}$ $=$ $\frac{\phi(n)}{x_i}$ ,as required.

This post has been edited 1 time. Last edited by Sprites, Aug 20, 2021, 5:53 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ChrisWren

323 posts

ChrisWren

#45 h Dec 1, 2021, 9:06 PM

Y by

$m=2^{20}\cdot 3^9\cdot 5^3\cdot 7^2\cdot 11^2$ works. We can let $\nu_{p}{(n)}$ equal $0$ or $1$ for every prime in $\{13, 17, 19, 23, 29, 31, 37, 41, 43, 61, 67\}$ and adjust the number of factors of $2,3,5,7,11$ in $n$ as needed.

The number $m$ is equivalent to $15296168853504000$

This post has been edited 1 time. Last edited by ChrisWren, Dec 1, 2021, 9:08 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5585 posts

megarnie

#46 h Mar 12, 2022, 1:40 PM • 1 Y

Y by GoodMorning

Solved with GoodMorning.

We claim $m=\boxed{2^{41}\cdot 3^{19}}$ works.

Let $S$ be the set of primes $\{5,13,17,37,73,97,109,163,193,577,769\}$ . We chose these primes because they are $1$ more than a power of $2$ times a power of $3$ . Note that $m=\varphi\left({\prod_{x\in S}x}\right)$ .

Claim: There exists a positive integer $x$ with $\varphi(x)=2^a\cdot 3^b$ , for all positive integers $a$ , nonnegative integers $b$ , and $a=b=0$ . Furthermore, $x$ has no prime factors except $2$ and $3$ .
Proof: Set $x=2^a\cdot 3^{b+1}$ . $\blacksquare$

Take any subset $T\subset S$ . We have $\frac{\varphi\left(\prod_{x\in S}x\right)}{\varphi\left(\prod_{x\in T}x\right)}=\varphi\left(\prod_{x\in S, x\not\in T}x\right)$ Note that this value can be written in the form $2^a3^b$ , where $a>0$ . Setting $n=2^a\cdot 3^{b+1}\cdot \prod_{x\in T}x$ gives $\varphi(n)=m$ . Also setting $n=\prod_{x\in S}x$ works.

There are $2^{11}-1=2047$ ways to choose $T$ , and one additional way, which gives at least $2048>2015$ different values of $n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CyclicISLscelesTrapezoid

372 posts

CyclicISLscelesTrapezoid

#47 h Apr 5, 2022, 7:07 PM

Y by

Oops.

We claim that $m=312 \cdot 408 \cdot 576 \cdot 660 \cdot 936 \cdot 1152 \cdot 1800 \cdot 1320 \cdot 1008 \cdot 1200=149967695669069120274432000000$ works.

Choose $n=a_1 \cdot a_2 \cdots a_{11}$ , where
$\begin{align*} a_1 &\in \{1,2\}\\ a_2 &\in \{313,3 \cdot 157\}\\ a_3 &\in \{409,5 \cdot 103\}\\ a_4 &\in \{577,7 \cdot 97\}\\ a_5 &\in \{661,11 \cdot 67\}\\ a_6 &\in \{937,13 \cdot 79\}\\ a_7 &\in \{1153,17 \cdot 73\}\\ a_8 &\in \{1801,19 \cdot 101\}\\ a_9 &\in \{1321,23 \cdot 61\}\\ a_{10} &\in \{1009,29 \cdot 37\}\\ a_{11} &\in \{1201,31 \cdot 41\} .\end{align*}$ Since there are $2^{11}>2015$ choices for $n$ , we are done.

This post has been edited 1 time. Last edited by CyclicISLscelesTrapezoid, Apr 5, 2022, 7:16 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

john0512

4180 posts

john0512

#48 h Mar 4, 2023, 6:35 AM

Y by

Am I getting trolled?

We claim that $m=2^{10000}3^{10000}$ works.

Consider the eleven primes $5,17,257,65537$ $7,19,163$ $13,37,109$ $73.$ Each of these primes has the property that the number 1 less than it contains no prime factors other than possibly 2 or 3. We will generate 2048 different $n$ for which $\phi(n)=2^{10000}3^{10000}$ in the following manner:

Take any subset of the aformentioned 11 primes (which there are 2048 of), multiply all of those primes, and then multiply that result by 6. Call this intermediate result $I$ . Clearly, $\phi(I)=2^a3^b$ for $a,b<10000.$ Then, since $I$ is already a multiple of 6, we then have $\phi(I\cdot 2^{10000-a}3^{10000-b})=2^{10000}3^{10000},$ which gives us a solution for each of the 2048 values of $I$ , so we are done

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

trying_to_solve_br

191 posts

trying_to_solve_br

#49 h Jul 5, 2023, 12:19 AM

Y by

Wait a minute..
Just take primes $p_1,p_2,...,p_2015$ such that $p_i$ does not divide $p_j - 1$ for all $i,j$ , this is possible by Dirichilet.

Now, take all the prime divisors $q_i$ of $p_i-1$ for all $i$ and let $C$ be a big integer. Take numbers $p_i.q_1^{a_1}.q_2^{a_2}...q_j^{a_j}$ , choosing $a_i$ in the following way: noticing $q_i\neq p_j$ for all $i,j$ by our choice, we choose $a_i$ such that $v_{q_i}(p_i-1)+a_i=C$ , which solves the problem as all the v_q's of the numbers are equal, and all the $q-1$ all cancel out.

This post has been edited 1 time. Last edited by trying_to_solve_br, Jul 5, 2023, 12:22 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

minusonetwelth

225 posts

minusonetwelth

#50 h Jul 15, 2023, 5:43 PM

Y by

For a positive integer $n=p_1^{\alpha_1}\cdot\ldots\cdot p_k^{\alpha_k}$ , we have that $\phi(n)=\left(p_1^{\alpha_1}-p_1^{\alpha_1-1}\right)\cdot\ldots\cdot \left(p_k^{\alpha_k}-p_k^{\alpha_k-1}\right)$ . Note that if we have $\phi(n)=x$ has at least $a$ solutions and $\phi(n)=y$ has at least $b$ solutions, then $\phi(n)=xy$ has at least $ab$ solutions as long as each of the $a$ solutions are coprime to each of the $b$ solutions. Letting the $a$ solutions for the first equation be $\{a_1,\ldots,a_a\}$ and the $b$ solutions for the second equation be $\{b_1,\ldots,b_b\}$ , we see that this is true because if $a_i$ and $b_j$ are coprime, then $\phi(a_i\cdot b_j)=\phi(a_i)\cdot\phi(b_j)$ . Therefore, finding enough numbers $m$ for which $\phi(n)=m$ has more than one solution will do the trick. For this,, just pick $\left\lceil\log_2(2015)\right\rceil=11$ pairs of paiwise distinct primes $p,q$ such that $r=(p-1)(q-1)+1$ is prime, and which are each also pairwise distinct from those constructed numbers $r$ (just do small cases, sorry

). As then $\phi(r)=\phi(pq)=(p-1)(q-1)$ , we get what we want.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#51 h Dec 29, 2023, 3:30 PM

Y by

I feel like I have some kind of obsession with Dirichlet now :/

Pick $2015$ primes $p \equiv 1 \pmod {10}$ by Dirichlet, and let $n$ be the LCM of $(p-1)^2$ for these primes multiplied by $10^{1000}$ . Notice that we have $\phi(n) = \phi\left((p-1) \cdot \frac n{p-1}\right) = \phi\left( p \cdot \frac n{p-1}\right)$ for each of these primes $p$ because $p-1$ divides $\frac n{p-1}$ . It follows that by varying across all $p$ we can construct $2015$ solutions to $\phi(k) =\phi(n)$ , as needed.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ryanbear

1055 posts

ryanbear

#52 h Jun 7, 2024, 12:41 AM

Y by

Let $n=30^{1434143414341434}$ .
Let $p$ be the product of any subset of $\{ 7, 11, 13, 17, 31, 37, 41, 61, 97, 151, 181\}$ besides $1$ . Note that there are $2047$ values of $p$ .
Note that $\phi(\frac{pn}{\phi(p)})=\phi(p)*\phi(\frac{n}{\phi(p)})=\phi(n)$ , since for all $p$ , $\phi(p)$ is the product of all the prime factors of $p$ minus one, which only has prime factors $2,3,$ or $5$ , so it divides $n$ and dividing by $\phi(p)$ does not impact the prime factors and only divides the final value by $\phi(p)$ , which is then multiplied back.
All values of $p$ work, which is more than $2015$ values.

This post has been edited 1 time. Last edited by ryanbear, Jun 7, 2024, 12:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1253 posts

ezpotd

#53 h Nov 20, 2024, 6:01 PM

Y by

Consider the $11$ pairs of primes $(3,5), (7,13), (31,61) ,(37,73) ,( 57,113), (79,147) , (97,193) , (139,277) , (157, 313) , ( 199,397), (211, 421)$ . The $2048$ numbers generated from picking one prime from each pair and taking the product have Totient functions differing by powers of $2$ , so it suffices to multiply each of those numbers by a power of $2$ , and we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lelouchvigeo

179 posts

lelouchvigeo

#54 h Dec 26, 2024, 6:07 AM

Y by

Nice Application of Dirichlet.Sketch

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8857 posts

HamstPan38825

#55 h Jan 4, 2025, 7:08 PM

Y by

Let $p_1, p_2, \dots, p_N$ be the first $N$ primes for some sufficiently large $n$ , and consider
$m=\phi(p_1p_2 \cdots p_N) = (p_1-1)(p_2-1)\cdots(p_N-1).$ The claim is that for all $N/2 < k < N$ , we can construct an $n$ such that $p_k \nmid n$ , $p_i \mid n$ for all $i \neq k$ , and $\phi(n) = m$ . Clearly these $n$ are distinct, so they exhibit our desired examples.

To do this, let $q_1, q_2, \dots, q_\ell$ be the maximal prime powers that divide $p_k - 1$ . By construction, for each $i$ there exists an index $j < k$ such that $q_i$ is equal to the $a_i$ th power of $p_j$ . Then taking
$n = (p_k - 1)\prod_{i \neq k} p_i$ works for each $k$ .

Remark: The construction for $n$ is oddly simplistic by number theory standards.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megahertz13

3182 posts

megahertz13

#56 h Feb 14, 2025, 3:06 AM

Y by

The value $m=(2-1)(3-1)(5-1)(7-1)\dots(k-1)$ works, where $k$ is the $2015$ th prime number. The values of $n$ that work are of the form $n=2\cdot 3\cdot5\cdot7\dots k\cdot\frac{p-1}{p}$ where $p$ is one of the first $2015$ primes. To prove that these work, notice that all the prime factors of $p-1$ are included in the other primes, so $\varphi(n)=(p-1)\varphi\bigg(\frac{2\cdot3\cdot5\dots k}{p}\bigg)=(p-1)\frac{\varphi(2)\varphi(3)\varphi(5)\dots\varphi(k)}{\varphi(p)}=m$ since $\varphi(p)=p-1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

zuat.e

41 posts

zuat.e

#57 h Apr 2, 2025, 9:44 PM

Y by

We generalise the problem for a sequence with at least $x$ solutions

Definition: For a sequence of primes $\{p_a\}$ , define the set
$P(\{(p_a-1)\})=\{q:q\mid p_i-1\}$

Claim
We can choose $\{p_a\}$ such that $p_i\neq q_j$ for all $i,j$ , where $q_j\in P(\{(p_a-1)\})$

Proof: We show we may always add another prime $p_{k+1}$ regardless of all previous $k$ primes.
Let $P(\{(p_a-1)\})=\{q_1,q_2,\dots q_t\}$ , therefore consider $p_{k+1}\equiv 1\pmod{q_1,q_2,\dots, q_t}$ (by $CRT$ ) and by Dirichlet we can obtain $p_{k+1}$ prime.

We now prove we can find $m$ such that $\phi (n)=m$ has at least $x$ solutions.
Let $\{p_a\}_{a=1}^{x-1}$ be a sequence of primes such that $p_i\neq q_j$ for all $i,j$ , where $P(\{(p_a-1)\})=\{q_1,q_2,\dots q_t\}$ and write:
$m=(p_1-1)(p_2-1)\dots (p_{x-1}-1)(q_1-1)(q_2-1)\dots (q_k-1)$

Clearly $n=p_1p_2\dots p_{x-1}q_1q_2q_{k}$ satisfies. Provided that $p_i-1=q_1^{\alpha_1}q_2^{\alpha_2}\dots q_k^{\alpha_k}$ , $n_i=\frac{n}{p_i}\cdot q_1^{\alpha_1}q_2^{\alpha_2}\dots q_k^{\alpha_k}$ also satisfies and clearly $n\neq n_i\neq n_j\neq n$ , getting at least $n, n_1, n_2\dots n_{x-1}$ as the $x$ desired solutions.

This post has been edited 1 time. Last edited by zuat.e, Apr 10, 2025, 5:55 PM

Z K Y