Remark: It is possible to generalize to $n^{2-\epsilon}$ through non-elementary methods, which is quite a surprising result.

We will actually prove the result for any constant $c$, provided $n$ is sufficiently large. Choice of $n$. First, we use the following result. Claim: If $\ell$ is any prime, there is a prime $p > \ell$ with $p \equiv 1 \pmod{\ell-1}$, such that $p < \exp(\ell/2c)$. Proof. In fact Linnik's theorem on the progression $1 \pmod{2\ell-1}$ implies we can get such a prime $p$ with $p < O(\ell^5)$. $\blacksquare$ Let $(\ell, p)$ be as in the claim and let \[ n = p-1. \] Choice of integer which cannot be a sum. Let $b \pmod{\ell}$ be chosen such that $ip \not\equiv b-1, b, b+1 \pmod{\ell}$ for any $1 \le i \le c\log p$: such $b$ exists since there are at most $3c\log p < \ell$ bad choices of $b$. Then, let $T$ be any integer with \begin{align*} T &\equiv -1 \pmod p \\ T &\equiv b \pmod \ell. \end{align*}Suppose $T = x_1^{p-1} + x_2^{p-1} + \dots + x_k^{p-1}$ is a sum of $k$ coprime $n$th powers. Claim: We have $k \equiv 0 \pmod p$ or $k \equiv -1 \pmod p$. Proof. Any $(p-1)$th power is $0 \pmod p$ or $1 \pmod p$ and there is at most one such power divisible by $p$, so the first part follows. $\blacksquare$ Claim: We have $k \equiv b-1 \pmod \ell$ or $k \equiv b \pmod \ell$. Proof. Since $\ell-1 \mid p-1$, we also know any $(p-1)$th power is $0$ or $1$ modulo $\ell$, and the $0$ case happens at most once. So the same analysis modulo $\ell$ gives the second part. $\blacksquare$ The first claim means $k \in \{ p-1, p, 2p-1, 2p, \dots\}$. Our choice of $b$ ensures that the first $c\log p$ such choices all fail modulo $\ell$; so we have $k > (c \log p + 1) \cdot p - 1 > cn \log n$ as needed.

Here's a further generalization: we solve the problem for $cn(\log n)^d$, for any $c\geq 0,d\geq 1$ (with $d$ as an integer, but the non-integral cases are simple to deal with by taking $\lceil d\rceil$). The idea is to limit the number of values $x^n$ takes modulo some number $m$ - in particular, call a pair of integers $(n,m)$ Will if $x^n\equiv 0,1\pmod p^k$ for $p^k\mid\mid m$. Our goal is to show the existence of infinitely many Wills with $m>\text{large}\cdot n\log n$ (large will be defined right now). In particular, we note that if $m$ has $\omega(m)$ different factors such that $\phi(p^k)\mid n$ for any $p^k\mid\mid m$, then there are $2^{\omega(m)}$ such possible residues given that $m>2^{\omega(m)}cn(\log n)^d$. The main trick here is to realize what we want - we want to restrict $\omega(m)$, so we choose $\omega(m)=kd+1$ for some $k\geq 1$, for some $k$ specified later (so that we can choose $c$). We choose $p$ distinct primes dividing consecutive Fermat numbers - the reason behind this is that we can continuously reduce $n$, as we know that any prime divisor of $2^{2^x}+1$ is congruent to $1\pmod{2^x}$. This gets rid of the superfluous $2^{\omega(m)}$, while converting $\frac mn$ very large. Formalizing this is not hard - choose $2d$ such primes ($p_1<p_2<\cdots<p_{kd+1}$), and suppose the smallest Fermat number was $2^{2^x}+1$. Then, we can choose $m$ as the product of such primes, while \[n=2^{-\left[x+(x+1)+\cdots+(kd+x-1)\right]}\prod_{i=1}^{kd+1} (p_i-1)=2^{-\frac 12\cdot kd\cdot (kd+2x-1)}\prod_{i=1}^{kd+1} (p_i-1)\]Note that clearly $n$ is an integer, as we noted that we have these superfluous powers of $2$ being multiplied as $2^{x-1+i}\mid p_i-1$, while we clearly don't need these powers. This furthermore shows that we can approximate that \[\log_2(n)^d<\left(2^x+2^{x+1}+\cdots+2^{kd+x-1}-\left[x+(x+1)+\cdots+(kd+x-1)\right]\right)^d\]The best thing to do right now is to note the amount of leeway we are given in such a Will, and also note we ideally want to compare to $\frac mn>2^{\frac 12(kd)(kd+x)}=2^{(kd+x)d}\cdot 2^{\frac{k-2}2(kd+x)}$ (given, of course, $k\geq 3$). Fortunately, we easily get that $\log_2(n)^d<2^{(kd+x)d}<2^{\frac{k-2}2}\frac mn$, which shows that in an overkill, such a Will provides the strong bound \[m>2^d\cdot 2^{\frac{k-2}2kd}n(\log n)^d\]As $k$ was at least $3$ but up to our choosing, we are free to make it large enough such that $2^d\cdot 2^{\frac{k-2}2kd}>c$.

This problem was proposed by Matthew Brennan (SnowEverywhere), Canada. Fun fact: it was also Ben Green's favourite shortlist problem, as to him it felt like the the closest to an actual research problem.

$cn log n$ can be achieved by taking prime factors of Fermat numbers. Take any prime divisor $p|2^{2^m}+1 (m \ge 4)$, and $n=p-1$. Note that $x^{p-1} \equiv 0,1 (mod p)$ and $x^{p-1} \equiv 0,1 (mod 2^{m+2})$. If $N$ can be expressed as the sum of $k$ coprime $p-1$th powers, then $N\equiv k,k-1 (mod p)$ and $N\equiv k,k-1 (mod 2^{m+2})$, thus $k-N \equiv 0,1,A,B (mod p2^{m+2})$ for some $A,B$. Hence there exists $N (mod p2^{m+2})$ such that the minimum possible value of $k$ is at least $\frac{1}{4} \times p 2^{m+2}\ge Cplog p. \quad\blacksquare$

Comment: The mod part is quite nice. However, if you know some basic analytic NT, you can strengthen the bound to $n^{2-\varepsilon}$ without much effort, which is what I did below. Take a large positive integer $M$ and let $P = \prod_{p <M} p$ where the product runs through prime. Take. $$n = \text{lcm}_{p<M} (p-1).$$First, we give the asymptotic results of $P,n$. Lemma 1: $\log P = M + O\left(\tfrac{M}{\log M}\right)$ Proof: This is equivalent to prime number theorem. The reduction to PNT can be found in most Analytic NT textbooks. $\blacksquare$ Lemma 2: $\log n \leq \frac{M}{2} + O\left(\tfrac{M}{\log M}\right)$ Proof: The trick is to note that $p-1$ is even for $p>2$ thus \begin{align*} n &\leq 2\cdot\mathrm{lcm}(1,2,\hdots,M/2) \\ &\leq 2\cdot\prod_{p<M/2} p \cdot \prod_{p<\sqrt{M}} p^{\log_p M} \\ &= \left(\prod_{p<M/2} p\right) \cdot e^{O(\sqrt{M}\log M)} \end{align*}Thus using Lemma 1 gives the result. $\blacksquare$ Now we give the key idea. Suppose that we use $k$ perfect powers, then for each $p<M$, each power must $\equiv 0,1\pmod p$ but at most one is $\equiv 0\pmod p$. Thus the sum must be $\equiv k,k-1\pmod p$. By CRT, the sum of $k$ perfects powers cover at most $2^{\pi(M)}$ residues modulo $P$. Hence we have to use at least $$N = \frac{P}{2^{\pi(M)}} = e^{M+O(M/\log M)}$$perfect powers. This is greater than $n^{2-\varepsilon}$ for all sufficiently large $M$. Remark: One can improve the bound quickly to $n^c$ for any constant $c$, by selecting only primes that are $\equiv 1\pmod N$ (where $N$ is a product of primes, large enough so that $N/\varphi(N)>c$) and use PNT on arithmetic progression.

v_Enhance wrote: We will actually prove the result for any constant $c$, provided $n$ is sufficiently large. Choice of $n$. First, we use the following result. Claim: If $\ell$ is any prime, there is a prime $p > \ell$ with $p \equiv 1 \pmod{\ell-1}$, such that $p < \exp(\ell/2c)$. Proof. In fact Linnik's theorem on the progression $1 \pmod{2\ell-1}$ implies we can get such a prime $p$ with $p < O(\ell^5)$. $\blacksquare$ Let $(\ell, p)$ be as in the claim and let \[ n = p-1. \] Choice of integer which cannot be a sum. Let $b \pmod{\ell}$ be chosen such that $ip \not\equiv b-1, b, b+1 \pmod{\ell}$ for any $1 \le i \le c\log p$: such $b$ exists since there are at most $3c\log p < \ell$ bad choices of $b$. Then, let $T$ be any integer with \begin{align*} T &\equiv -1 \pmod p \\ T &\equiv b \pmod \ell. \end{align*}Suppose $T = x_1^{p-1} + x_2^{p-1} + \dots + x_k^{p-1}$ is a sum of $k$ coprime $n$th powers. Claim: We have $k \equiv 0 \pmod p$ or $k \equiv -1 \pmod p$. Proof. Any $(p-1)$th power is $0 \pmod p$ or $1 \pmod p$ and there is at most one such power divisible by $p$, so the first part follows. $\blacksquare$ Claim: We have $k \equiv b-1 \pmod \ell$ or $k \equiv b \pmod \ell$. Proof. Since $\ell-1 \mid p-1$, we also know any $(p-1)$th power is $0$ or $1$ modulo $\ell$, and the $0$ case happens at most once. So the same analysis modulo $\ell$ gives the second part. $\blacksquare$ The first claim means $k \in \{ p-1, p, 2p-1, 2p, \dots\}$. Our choice of $b$ ensures that the first $3c\log p$ such choices all fail modulo $\ell$; so we have $k > (c \log p + 1) \cdot p - 1 > cn \log n$ as needed. I'm pretty sure Linnik's theorem is a bit overkill here: by taking the $2\ell-2$ cyclotomic polynomial at 2 and using Zsigmondy's theorem, we get a prime bigger than $\ell$ that is $1 (\mod \ell-1)$, and it is at most $3^{\phi (2\ell-2)}$.

Let $p$ be a prime, and $q$ another prime satisfying $q \equiv 3p-2 \mod p(p-1)$. By Linnik's Theorem, there exists such a $q<O((p(p-1)^k) < O(p^d)$ for some fixed constant $d$. Hence, $p > \Omega(q^\frac{1}{d}) >\Omega(\log q)$. Now, let $n=q-1$, we have that $p-1 \hspace{0.3em} | \hspace{0.3em} q-1=n$. I claim that all $x \equiv p \mod p^n$ cannot be expressed with fewer than $cn\log(n)$ $n$th powers. Suppose $x=x_1^n+x_2^n + \cdots x_t^n$ for some integer $t$. Note that at most one of the $x_i$ can be $0 \mod p$ (it cant be the only one as $x$ is not divisible by $p^n$), and furthermore the rest of the terms must be $\equiv 1 \mod p$. Thus, number of $x_i$ not divisible by $p$ is divisible by $p$. Similarly, the number of $x_i$ not a multiple of $q$ is divisible by $q$. Thus, we can either write $t=ap=bq$ , $t=ap=bq+1$ or $t=bq=ap+1$, for some positive integers $a,b$. Hence, either $b \equiv 0 \mod p$, $b \equiv -q^{-1} \equiv \frac{p-1}{2} \mod p$ or $b \equiv q^{-1} \equiv \frac{p+1}{2} \mod p$. In any case, $b \ge \frac{p-1}{2}$, so $t =bq \pm 1 =\Omega(pq) > \Omega(q\log q) = \Omega(n\log n)$ as desired.

We prove this for all $c$. Choose a prime $q$, and a prime $p$ by Dirichlet's such that $q - 1 \mid p - 1$. By density we can guarantee that $(3 + \varepsilon)c \log p < q$ infinitely many times. Take $n = p - 1$ for some prime $p$ and let $k = cn \log n$ ranges from $1$ to $m$. As such, \[ a_1^n + a_2^n + \dots + a_k^n \equiv k-1, k \pmod{p} \equiv k - 1, k \pmod{q}. \]so this covers at most $3k + 1 < (3 + \varepsilon)p \log p$ residues.

Very nice construction problem, i claim $c=(\ln(2))^{-1}$ does the work. Built a set of primes $p_1,p_2,p_3,....$ such that $p_1>1434$ and $p_{i+1}$ is defined as the least prime that belongs to the aritmethic sequence $n(p_i-1)+1$ for all $i$ positive integers, now note that by Zsigmondy it holds that $2^{p_i-1}-1 \ge p_{i+1}$ for all $i$ positive integers, this implies that $p_i>\text{log}_2(p_{i+1}-1)$, now notice $\text{lcm}(p_1-1,p_2-1,...,p_i-1)=p_i-1$ so if our pairwise coprime $p_i-1$-th powers are the $a_i$'s then: $$a_1^{p_i-1}+a_2^{p_i-1}+...+a_k^{p_i-1} \equiv k \; \text{or} \; k-1 \pmod{p_l} \; \forall 1 \le l \le i$$Let $P_i=\prod_{j=1}^{i} p_j$ then by CRT we have that $a_1^{p_i-1}+...+a_k^{p_i-1} \pmod{P_i}$ yelds at most $2^i$ residues hence u need at least $P_i \cdot 2^{-i}$ pairwise coprime $p_i-1$-th powers. But now note that: $$P_i \ge 2^i \cdot P_{i-2} \cdot p_{i-1} \cdot p_i>2^i \cdot (p_i-1)\text{log}_2(p_i-1)$$Hence u need at least $\frac{P_i}{2^i} \ge \frac{1}{\ln(2)} \cdot (p_i-1)\ln(p_i-1)$ pairwise coprime $p_i-1$-th powers so setting $n=p_i-1$ for all $i \ge 1434^{1434}$ is enough to solve the problem .

bleh We prove this for $c=1$, but in fact any $c$ works. Let $p_1<p_2<\cdots$ be the primes. Let $M$ be a large positive integer; define $P=\prod_{i \leq M} p_i$ and pick $n=\mathrm{lcm}\{p_i-1\}_{i \leq M}$. I claim that this works. This hinges on the following claim. Claim: As $M \to \infty$, we have $\frac{n\log(n)\cdot 2^M}{P}=o(1)$. Proof: We upper bound the size of $n$. The key idea is to note that the LCM will not get multiplied by $p_i-1$ every time we increase $i$, but instead often gets multipled by a smaller factor. We create an upper bound for this LCM as follows: when we increase $i$, multiply the previous estimate by $p_i$ (not $p_i-1$). Then, we may make the following adjustements: If $p \not \equiv 1 \pmod{4}$, for large enough $M$ we can divide our estimate by $2$, since $\nu_2(p_i-1)$ is certainly less than $\nu_2(n)$. By Chebotarev density this happens $1/2$ of the time. If $p \equiv 4,7 \pmod{9}$, for large enough $M$ we can divide our estimate by $3$ for the same reason. By Chebotarev density this happens $1/3$ of the time. The asymptotic of our upper bound on $n$ is then $\frac{P}{(2^{1/2}\cdot 3^{1/3})^M}$. Let $C=2^{1/2}\cdot 3^{1/3}>2$. It is well-known that $P \sim e^{M \log M}$, so $$\frac{n \log(n)\cdot 2^M}{P}=O\left(\frac{\frac{P}{C^M}(M\log M-M\log C)2^M}{P}\right)=O\left((2/C)^M(M\log M)\right)=o(1).~\blacksquare$$ We now return to the main problem. I claim that for large enough $M$ there exists some modulo-$P$ residue which cannot be written as the sum of fewer than $n\log(n)$ pairwise coprime $n$th powers. Due to the definition of $n$, each $n$th power modulo $p_i$ for any $i \leq M$ is either $0$ or $1$. If we sum $k$ pairwise coprime $n$th powers, for each prime $p_i$ a zero can occur at most once (this is the only time the coprime condition gets used). Therefore there are $2^M$ possible mod-$P$ residues attainable for this value of $k$ (by CRT), since there are exactly two choices for the sum modulo $p_i$ for any $i \leq M$. Since we have $n\log(n)$ choices for $k$, it follows that we hit at most $n\log(n)\cdot 2^M$ residues modulo $P$. By our claim, for all sufficiently large $M$ this is less than $P$, finishing the problem. $\blacksquare$

MarkBcc168 wrote: Remark: One can improve the bound quickly to $n^c$ for any constant $c$, by selecting only primes that are $\equiv 1\pmod N$ (where $N$ is a product of primes, large enough so that $N/\varphi(N)>c$) and use PNT on arithmetic progression. Does anyone know if there is an even better lower bound than $n^c$? What about an upper bound? (Also asked at: https://mathoverflow.net/questions/378543/warings-problem-with-pairwise-coprime-summands)

Define $P_N$ as the product of the first $N$ primes, $p_i$ as the $i$th prime and $L_N = \mathrm{lcm}(p_1 - 1, p_2 - 1, \dots, p_N - 1)$. If $p-1 \mid n$ for some prime $p$ then $x^n$ must equal $0$ or $1 \pmod{p}$ which implies that the sum of any $k$ coprime $n$th powers is equal to $k-1, k \pmod{p}$. This is because we can't have more than one $k$th power equivalent to $0\pmod{p}$ due to the coprime condition. So by CRT for every choice of $k$ there are $2^N$ possible residues modulo $P_N$ for the sum of powers, and multiplying by $cn\log(n)$ gives us a total of $2^N \cdot cn\log(n)$ possible residues. We wish to find $n$ so that \(\frac{2^N \cdot cn\log(n)}{P_N} < 1\). We will show that for sufficiently large $N$, $n = L_N$ works. We can bound $L_N$ by noticing that we overcount \(\nu_2(p_i - 1) \geq 1\) $N - 2$ times by considering $p_i - 1$ for all $i > 2$, so we get \(\frac{P_N}{2^{N-2}} \geq L_N\). Also notice that we overcount \(\nu_3(p_i - 1)\) at least twice (shocking, right?) by considering $p_4 - 1 = 6$, $p_6 - 1 = 12$, and $p_8 - 1 = 18$. So we get the bound \(\frac{P_N}{9 \cdot 2^{N-2}} \geq L_N = n\). Let \(\frac{2^N}{9 \cdot 2^{N-2}} = \epsilon < 1\). Plugging in our previous bound into \(\frac{2^N \cdot cn\log(n)}{P_N}\), we get \[ \frac{2^N \cdot cn\log(n)}{P_N} = O\left(\epsilon^N \cdot c \log(P_N)\right) = O\left(\epsilon^N \cdot O(N\log N)\right) = o(1) \]as desired.

For a large $M$ pick $n=LCM(1,2,....,p_M-1)$ where $p_i$ is the $i$th prime. we show this works. By chinese remainder theorom we know we for any $e_1,e_2,.....,e_M$ there exists infinitely many $L \equiv e_i$(mod $p_i^{k_i}$) where $k_i=1+$ exponent of $p_i$ in $n$ We prove for any such choice of $L$ if $L=(a_1)^{n}+......+(a_k)^{n}$ Then Lemma1 : the remainder when $k$ is divided by $p_i^{k_i}$ is $e_i$ or $e_i+1$ Observe $(a_i)^{n} \equiv 1$(mod $p_i^{k_i}$) exactly when $a_i$ is not divisible by $p_i$[otherwise its $0$] by eulers theorom . For $\phi{(p_i^{k_i})}=p_i^{k_i-1}(p_i-1)|n$ , so if all $a_i$ is not divisible by $p_i$ we know $L \equiv k$(mod $p_i^{k_i}$) so it works in that case , and if one of them is divisible by $p_i$ there is at max $1$ one such $a_i$[due to pairwise coprime] , so then $k \equiv L+1$(mod $p_i^{k_i}$) , hence finsihing the proof of our lemma. Lemma 2: For a suitable choice of $e_1,e_2,...,e_M$ the smallest $k$ which will satisfy the congruence relation will be atleast $\frac{n(p_1p_2....p_M)}{C^M}$ . for a constant $C$ The idea is to parition the residue class of $(p_i)^{k_i}$ into pairs of consequtive numbers , that is like $(0,1),(2,3),....,((p_i)^{k_i}-3,(p_i)^{k_i}-2)$ which is atleast $\frac{(p_i)^{k_i}-1}{2} > \frac{(p_i)^{k_i}}{C}$ such pairs for a large enough constant $C$ . [if $p_i=2$ then the parition does not work like this its a bit different however that dosent affect the bounds] Now as we choose any such $e_i$'s from the those **disjoint** pairs[such that $(e_i,e_{i}+1)$ becomes that pair] , we will end up with atleast $\frac{n(p_1p_2....p_M)}{C^M}$ positive distinct solutions[as for the pairs were disjoint no two solutions could be equal] , so one of solutions will be atleast $\frac{n(p_1p_2....p_M)}{C^M}$ , finsihing the proof of the lemma . With that we prove the main problem Now we know $k \geq \frac{n(p_1p_2....p_M)}{C^M}$ infinitely often for a fixed $M$ . It suffices to show $\frac{n(p_1p_2....p_M)}{C^M} \geq \mathcal{O}(n log (n))$ for a large enough $M$ $\iff \frac{p_1p_2.....p_M}{C^M} \geq \mathcal{O}(log(n))$ as $n \leq p_M^{p_M}$ [this looks so cursed ] It suffices to show $ \frac{p_1p_2....p_M}{C^M} \geq \mathcal{O}(p_M log(p_M))$ SO we can just show that $e^{\frac{p_1p_2....p_M}{C^M}} \geq p_M^{p_M *C_2}$ for a suitable choice of $C_2$ or that $e^{\frac{p_1p_2....p_{M-1}}{C^{M-1}}} \geq p_M^{C_2}$ [$C_2C$ is just another constant so i just wrote it as $C_2$] Its well know that $ p_i< 2^i$ for large $i$ a result that can be easily proved by bertands. By that as $M$ grows larger eventually $\Pi_{i=1}^{M-1} \frac{p_i}{C} \geq (p_M)^{T}$ for a large number $T$ and as $e^{x} \geq x$ for large enough $x$ and we are done.

We will prove the result for $cn^{1.9}$. Reduction to Analytic NT Let $k$ be a fixed large number and let $p_1<p_2<\dots$ denote all the primes in order. Also in this proof, we let $p$ denote a general prime. Now choose $n=\text{lcm}(p_1-1,p_2-1,\cdots,p_k-1)$ and let $Q=\prod_{p \leq p_k} p$. Assume this is false for this $n$, and for all large $N$, we can write it as $x_1^n+\dots+x_t^n$ (pairwise $x_i$ are relatively prime) and we have $t \leq cn^{1.9}$. clNow see that $x_i \equiv 0,1 \pmod {p_j}$ and atmost one of them can be $0$ mod some $p_j$; and this means we get that \[N \equiv t-1,t \pmod {p_j}\]and hence by CRT $N$ can take maximum $2^k$ residues modulo $Q$ and hence this means we can carefully choose $N \pmod Q$ such that $t \geq \frac{Q}{2^k}$ and this means that \[cn^{1.9} \cdot 2^k \geq Q \left(\clubsuit \right)\]Finish We will need two major lemmas. Lemma: We have \begin{align*} & \log Q \geq 0.999p_k \\ & \log n < 0.501 p_k \end{align*}Proof: First one is well known as $\log Q \sim p_k$ so just choose $k$ big as we did. For the second one, see that each $p_i-1$ is even for all $i \geq 2$ and hence we have \begin{align*} \log n & \leq \sum_{p \leq \sqrt{\frac{p_k}2}} \log p_k + \sum_{\sqrt{\frac{p_k}2}<p \leq \frac{p_k}2} \log p \\ & \leq {\frac{1.001 \sqrt{\frac{p_k}2}}{\log \sqrt{\frac{p_k}2}}} \log p_k+1.001 \left(\frac{p_k}2-\sqrt{\frac{p_k}2} \right)\\ & \leq 0.501 p_k \end{align*}$\square$ This means that $\clubsuit$ gives us \[\log c \geq \log Q - 1.9 \log n \geq 0.999p_k-1.9(0.501)p_k = 0.0471 p_k\]which is a contradiction.

Can anyone please check for fakesolve? I couldn't seem to find a solution using the Carmichael function, even though my solution looks similar to a lot of others. In the following solution, I'll try to find numbers $m, n$ such that for all integers $a$ coprime to $m$, \[a^n\equiv 1\pmod{m}.\]Then, I'll give a bound regarding $n$ and $m$, which will ultimately prove the problem. Solution. Denote the $k$th prime in increasing order as $p_k$, where $p_1=2$. Then, we define $m_k=\text{lcm}(p_1-1, p_2-1,\cdots, p_k-1)\prod_{i-1}^kp_i$ and $n_k=\lambda(m_k)$, where $\lambda$ is the Carmichael function. By the definition of the Carmichael function, we know that for all integers $a$ coprime to $m_k$, \[a^{n_k}\equiv 1\pmod{m_k}.\]Our next step is to calculate $\lambda(m_k)$. By properties of the Carmichael function, we can calculate its value with the least common multiple of its powers of prime factors, plugged into the function itself. Namely, if $m_k=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$, then \[\lambda(m_k) = \text{lcm}(\lambda(p_1^{\alpha_1}), \lambda(p_2^{\alpha_2}),\dots,\lambda( p_k^{\alpha_k}))=\text{lcm}(\lambda(2^{\alpha_1}), \phi(p_2^{\alpha_2}),\dots,\phi( p_k^{\alpha_k}))\]\[=\text{lcm}(2^{\alpha_1-2}, p_2^{\alpha_2-1}(p_2-1),\dots, p_k^{\alpha_k-1}(p_k-1))=\text{lcm}(2^{\alpha_1-2}, p_2^{\alpha_2-1}, p_2-1,\dots, p_k^{\alpha_k-1}, p_k-1)\]By the construction of $m_k$, $p_i^{\alpha_i - 1} | \text{lcm}(p_1-1, p_2-1,\cdots, p_k-1)$ for all $i = 1, 2, \cdots, k$. Hence, combined with the result above, \[n_k=\lambda(m_k)=\text{lcm}(p_1-1, p_2-1,\cdots, p_k-1).\]From here, since all $p_i-1$ are multiples of $2$, so $\text{lcm}(p_1-1, p_2-1,\cdots, p_k-1)\leq \frac{\prod_{i=1}^{k}(p_i-1)}{2^{k-2}}< \frac{\prod_{i=1}^{k}p_i}{2^{k-2}}$. Hence, $\frac{m_k}{n_k^2}>2^{k-2}$, and by Bertrand's Postulate (or whatever you wish since the bound is rather loose), we can find $c_t$ such that $2^{k-2}>c_t(\log n_k)^t$ for all $k$. For the last part, we try to bound the least amount of pairwise coprime $n_k$th powers needed to construct a number congruent to $-1$ modulo $m_k$. For a given combination of $n_k$th powers that satisfy this, we first add up the ones that aren't coprime with $m_k$. When we take the sum (say, $S$) modulo $p_i^{\alpha_i}$, by pairwise coprimality there exists at most one $n_k$th power that is divisible by $p_i^{\alpha_i}$, while the others are all congruent to $1$ modulo $p_i^{\alpha_i}$. Suppose there are $r$ $n_k$th powers in the sum that aren't coprime with $m$, then by the above either $S\equiv r \pmod{p_i^{\alpha_i}}$ or $S\equiv r-1\pmod{p_i^{\alpha_i}}$. This splits $p_1^{\alpha_1}, p_2^{\alpha_2}, \cdots, p_k^{\alpha_k}$ into two groups, namely group $S$ congruent to $r$ or $S$ congruent to group $r-1$. We can pick a group such that the product of its elements is larger than or equal to $\sqrt{m_k}$, and suppose the product is $P$. Then, if the remainder of $S$ when divided by $m_k$ is $R$, we have that $R-r + P\leq m_k$ since either $S-r$ or $S - r + 1$ is a multiple of $P$. The $n_k$th powers that are coprime with $m_k$ are congruent to $1$ modulo $m_k$ by construction, so in order for us to be able to construct a number congruent to $-1$ modulo $m_k$, we need to at least add $m_k-1-R\geq m_k-1-m_k-r+P\geq P-r-1\geq \sqrt{m_k}-r-1\geq \sqrt{m_k}-k-1>n_k\sqrt{c_t}(\log n_k)^{\frac{t}{2}}-n_k$. Now, when we pick $t>2$, we can find a constant $c$ that satisfies the original problem for all sufficiently large $n_k$. Hence, we are done.

We prove the result for $c = 1$. Claim: For any primes $p,q$ such that $q - 1 \mid p - 1$, the sum of fewer than $(p-1)\log(p-1)$ pairwise coprime $p-1$th powers cannot achieve more than $4p \log (p)$ residues modulo $pq$. Proof: Suppose otherwise. Let $a$ denote the residue modulo $pq$ that is $1 \pmod p$ and $0 \pmod q$, $b$ denote the residue modulo $pq$ that is $1\pmod p$ and $0\pmod q$, let $r$ be the remainder than $a +b $ is divided by $pq$, and let $x = \lfloor ((p-1) \log(p-1))$. We show that the remainder when the sum of less than $(p-1) \log(p-1) $ pairwise coprime $p-1$th powers is divided by $pq$ is in \[I = [0,x] \cup [a, a + x] \cup [b, b+x] \cup [c,c+x]\]Note that this would imply that it can only achieve at most \[4(x+1) < 4 ((p-1) \log(p-1) + 1) < 4 p \log(p) \]residues modulo $p$, which would prove the claim. It remains to show this fact is true. Suppose not and we had for some nonnegative integer $k < (p-1) \log(p-1)$ that \[s = x_1^{p-1} + x_2^{p-1} + \cdots + x_k^{p-1}\]was outside of these intervals modulo $pq$, where $x_1, x_2, \ldots, x_k$ are pairwise coprime. First we characterize $y^{p-1}$ modulo $pq$ for each integer $y$. If $y$ is divisible by $p$ and $q$, $y^{p- 1} \equiv 0 \pmod{pq}$ obviously. If $y$ is divisible by $p$ but not $q$, then by FLT, $y^{p - 1} \equiv 1 \pmod q$ but $y^{p - 1} \equiv 0 \pmod p$, so $y^{p - 1} \equiv b\pmod{pq}$. Similarly, if $y$ is divisible by $q$ but not $p$, $y^{p - 1}$ is $0 \pmod q$ and $1 \pmod p$, so $y^{p - 1} \equiv a\pmod{pq}$. Now, by FLT again, if $\gcd(y,pq) = 1$, $y^{p - 1}$ is $1\pmod p$ and $1 \pmod q$, so it must be $1 \pmod{pq}$. The characterization of $y^{p - 1}$ modulo $pq$ can be written as \[ \begin{cases} 0 & \text{ if } pq \mid y \\ a & \text{ if } p\nmid y \text{ and } q\mid y \\ b & \text{ if } p \mid y \text{ and } q\nmid y \\ 1 & \text{ if } p\nmid y \text{ and } q \nmid y \\ \end{cases} \]If $k = 0$ or $k = 1$, then the sum must be in $\{0, 1, a, b\}$ modulo $pq$, which are all in $I$, absurd. Therefore $k > 1$. Note that there can only be two numbers in $x_1, x_2, \ldots. x_k$ that are not relatively prime to $pq$. Thus, we can WLOG assume that everything except $x_1, x_2$ is not divisible by $p$ or $q$. Thus for any $i > 2$, $x^{p-1}$ is $1 \pmod p$ and $1 \pmod q$ by FLT (because $q - 1 \mid p- 1$). We can rewrite $s$ as \[ x_1^{p - 1} + x_2^{p - 1} + k - 2 \pmod{pq}\]Now, we additionally have that $p$ only divides at most one of $x_1, x_2$, so WLOG that $q\nmid x_2$. Case 1: $p\nmid x_2$. In this case, $s$ becomes \[ x_1^{p - 1} + k - 1 \pmod{pq} \]By our previous characterization, \[s \in \{k - 1, k, a + k - 1, b + k - 1\} \pmod{pq},\]which are all clearly in $I$, a contradiction. Case 2: $p\mid x_2$ In this case, $s$ becomes \[ x_1^{p - 1} + b + k - 2 \pmod{pq}\]Note that since $p\nmid x_1$, our characterization gives that \[ s \in \{b + k - 1, c + k - 2 \} \pmod{pq},\]which are all clearly in $I$, a contradiction. Therefore, $s \pmod{pq}$, must be in $I$, so our claim is proven. $\square$ Claim: $2^{36} < e^{30} $ Proof: This is equivalent to showing $2^6 < e^5$, which is evident as \[ e^5 > (2.7)^5 = \frac{27^5}{10^5} = 143.48907 > 64 = 2^6 \ \ \ \square\] Claim: For every large enough prime $q \equiv 1 \pmod{30}$, there exists a prime $p$ such that $p^4 < e^q$ and $q - 1\mid p - 1$. Proof: Let $p$ be a primitive prime divisor of $2^{q - 1} - 1$ (by primitive prime factor, we mean that $p\nmid 2^k - 1 \forall 0 < k < q - 1$), which exists by Zsigmondy since $q > 7$. Note that the order of $2$ modulo $p$ is $q - 1$, so $q - 1 \mid p - 1$. Additionally, let $q = 30t + 1$. We have \[ 2^{q - 1} - 1 = 2^{30t} - 1 = (2^{15t} + 1)(2^{15t} - 1) \]Note that $p$ cannot divide $2^{15t} - 1$, so \[ p\mid 2^{15t} + 1 = (2^{3t} + 1)(2^{4t} - 2^{3t} + 2^{2t} - 2^t + 1)(2^{8t} + 2^{7t} - 2^{5t} - 2^{4t} - 2^{3t} + 2^t + 1)\]Clearly $p$ must divide one of the three factors in the RHS, each of which is less than $2^{9t}$ for large enough $t$, so $p < 2^{9t}$. We now have $p^4 < 2^{36t} < e^{30t} < e^q, $ as desired. $\square$ Let $N$ be a constant so that for all $q > N$ with $q \equiv 1 \pmod{30}$, the condition in the previous claim holds. Now we claim for any integer $M$, there exists a working value of $n$ greater than $M$. Let $q > \max(M,N)$ be a prime so that $q \equiv 1 \pmod{30}$ and $p$ be another prime with $q - 1 \mid p - 1$ and $p^4 < e^q$. We claim that $n = p -1$ works. Notice that by our first claim, the sum of less than $(p-1) \log(p-1)$ powers of $p - 1$ can achieve at most $4 p \log(p)$ residues modulo $pq$. Now, we note that $q > \log(p^4) = 4 \log(p)$, so $pq > 4p \log(p)$, meaning that there must be a residue $r$ modulo $pq$ that cannot be achieved when summing less than $(p-1) \log(p-1)$ powers of $p - 1$. Since there are infinitely many positive integers $r \pmod{pq}$, $n = p - 1$ must work, so we are done.