For each $n$, define $L(n)$ to be the number of natural numbers $1\leq a\leq n$ such that $n\mid a^{n}-1$. If $p_{1},p_{2},\ldots,p_{k}$ are the prime divisors of $n$, define $T(n)$ as $(p_{1}-1)(p_{2}-1)\cdots(p_{k}-1)$. a) Prove that for each $n\in\mathbb N$ we have $n\mid L(n)T(n)$. b) Prove that if $\gcd(n,T(n))=1$ then $\varphi(n) | L(n)T(n)$.
Problem
Source: Iranian National Olympiad (3rd Round) 2006
Tags: abstract algebra, group theory, number theory proposed, number theory
26.08.2006 12:18
(b) suggests that in (a) you actually meant $\varphi(n)|L(n)T(n)$. (a) In general, in a finite abelian group (it's true for non-abelian groups as well, but it should be significantly harder to prove), if $t\ |\ |G|$, then the number of elements $x$ such that $x^{t}=1$ is a multiple of $t$. We apply this to the group $G=(\mathbb Z/n\mathbb Z)^\times$ of invertible residues modulo $n$ with $t=(n,\varphi(n))$. If $n=p_{1}^{a_{1}}\cdot\ldots\cdot p_{k}^{a_{k}}$, then by the above, $p_{1}^{a_{1}-1}\cdot\ldots\cdot p_{k}^{a_{k}-1}\ |\ (n,\varphi(n))\ |\ L(n)\ (*)$. After multiplying the leftmost and the rightmost terms in $(*)$ by $T(n)$ we get $\varphi(n)|L(n)T(n)$. (b) In this case, $a^{n}=1$ (in the group $G$) iff $a^{\frac{\varphi(n)}{T(n)}}=1\ (\#)$. $G$ is the direct product of a group of order $\frac{\varphi(n)}{T(n)}$ and one of order $T(n)$, and these orders are coprime. This means that the solutions to $(\#)$ are precisely the elements of the former group, so there are $\frac{\varphi(n)}{T(n)}$ of them. The desired result follows.
05.01.2007 11:31
I think there is a strongly result: $L(n)T(n)=\varphi(n)\prod_{i}\left(p_{i}-1,\frac{n}{p_{i}^{e_{i}}}\right)$ where $n=\prod_{i}p_{i}^{e_{i}}$ Someone confirm it?
20.10.2014 08:33
How to prove this: grobber wrote: In general, in a finite abelian group (it's true for non-abelian groups as well, but it should be significantly harder to prove), if $t\ |\ |G|$, then the number of elements $x$ such that $x^{t}=1$ is a multiple of $t$.
11.05.2017 00:03
a) Note that that if $p_i\mid a^n-1$ $\implies$ $v_{p_i}(n)\mid a^n-1$ simply because of LTE and the fact that order is coprime with $p_i-1$.Note that by previous once we found the solution set modulo each prime the rest is just shifting by $\text{rad}(n)$ $\implies$ $\frac{n}{\text{rad}(n)}\mid T(n)$ and so the conclusion. b) We show that $L(n)T(n)=L(n)\frac{n}{\text{rad}(n)}\prod_{i=1}^k \left(\frac{n}{v_{p_i}(n)},p_i-1 \right)$ which will effectively end it.$a^n=1$ in $\mathbb{F}_{p,{\times}}$ and so $\text{ord}(a)\mid \frac{n}{v_p(n)}$ but all such numbers are solutions to $X^{\frac{n}{v_p(n)}}-1$ which has $\left(\frac{n}{v_{p_i}(n)},p_i-1 \right)$ solutions and now using CRT and the note from a) we're done.
11.05.2017 15:12
@Boll, I agree: By CRTing roots of $x^n-1$ modulo prime-power divisors of $n$, and the fact that $(\mathbb Z/p^k\mathbb Z)^\times$ is cyclic under multiplication: $$L(n)=\prod \gcd\left(n,\varphi(p_i^{e_i})\right)=p_i^{e_i-1}\gcd\left(\frac{n}{p_i^{e_i-1}},p_i-1\right)$$At which point we are basically done.