[seqfan] Re: A050384

[Max Alekseyev]

Hi David,

The short answer is Yes. The proof follows from the two lemmas below.

Let M be the set of nonprimes m for which n^n == r (mod m) is soluble for
all r.

Lemma 1. Let m belong to A050384, then m belong to M.

Proof. Let m be any element of A050384.
Fix any r. Let d = gcd(m,r) and m = d*q. Since m as an element of
A050384 is square free, we have gcd(d,q)=1 and gcd(r,q)=1.
Furthermore, since d|m, phi(q)|phi(m), and gcd(m,phi(m))=1, we have
gcd(d,phi(q))=1.
Consider the system of three congruences:
n == r (mod q)
n == 1 (mod phi(q))
n == 0 (mod d)
Since its modules are pairwise coprime, the system is soluble.
Furthermore, it is easy to check that its solution n satisfies n^n ==
r (mod m). Indeed, n == 0 (mod d) guarantees n^n == r == 0 (mod d),
while n == r (mod q) and n == 1 (mod phi(q)) together with gcd(r,q)=1
imply that n^n == r (mod q).
Since r was chosen arbitrary, we proved that m belongs to M.
QED

Lemma 2. If m does not belong to A050384, then m does not belong to M.

Proof. Let m be any positive integer not from A050384. Consider two
cases depending on whether m is squarefree:

Case 1. If m is not squarefree, then k^2|m for some k>1. Then the
congruence n^n == k (mod m) is not soluble (for n>1, the r.h.s. and m
are divisible by k^2, but l.h.s. is not).

Case 2. If m is squarefree, take p be any prime dividing
gcd(m,phi(m)). Let m=p*q, where gcd(r,q)=1. Since
p|phi(m)=(p-1)*phi(q), we have p|phi(q).
Let r=p*k for 1<=k<q. So there are phi(q) values of r and they all are
pairwise distinct modulo q, since gcd(p,q)=1.
Assume that the congruence n^n == r (mod m) is soluble for any our r.
Then it splits into n^n == r (mod p) and n^n == r (mod q).
The former is equivalent to p|n, while the latter implies r ==
(n^(n/p))^p (mod q), i.e., r is the power p residue modulo q. So we
constructed q-1 such residues, but in reality the number of such
residues is phi(q)/p <= (q-1)/p < q-1. The contradiction proves that
not every n^n == r (mod m) is soluble, and so m does not belong to M.
QED

Regards,
Max


On Tue, Sep 29, 2015 at 6:31 AM, David Wilson <davidwwilson at comcast.net> wrote:
> Is A050384 the set of nonprimes m for which n^n == r (mod m) is soluble for
> all r?
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/