For every natural number $ n $, define $ s(n) $ as the smallest natural number so that for every natural number $ a $ relatively prime to $n$, this equation holds: \[ a^{s(n)} \equiv 1 (mod n) \] Find all natural numbers $ n $ such that $ s(n) = 2010 $
Problem
Source:
Tags: number theory, least common multiple, function, relatively prime, number theory unsolved
08.12.2010 17:57
Are you allowed to post this and discuss it openly? Maybe $s(n)$ is this.
08.12.2010 18:25
\[s(\prod_p p^{v_p(n)})=\textrm{lcm}_{p|n} (p-1)p^{v_p(n)-1}.\]$2010=2*3*5*67$. Therefore $s(n)=2010$ if $v_2(n)\le 3, v_3(n)\le 2,v_7(n)\le 1,v_{31}(n) \le 1,v_{2011}(n)=1$. There are $48$ numbers, such that $s(n)=2010.$
10.12.2010 06:02
@Lei2: of course, the problem had also been posted in another forum before...
11.12.2010 10:37
I'm sorry... How do you obtain that formula? I get that s(8)=2, but the formula gives s(8)=4 maybe I have made a mistake
29.07.2011 13:14
The function $s(n)$ is in fact Carmichael's function $\lambda(n)$; see http://en.wikipedia.org/wiki/Carmichael_function. Indeed $\lambda(p^k) = \varphi(p^k) = (p-1)p^{k-1}$ for an odd prime $p$, and $\lambda(2) =1$, $\lambda(2^2) =2$, $\lambda(2^k) =2^{k-2}$ for $k\geq 3$. And $\lambda\left (\prod_{j=1}^s p_j^{k_j}\right ) = \textrm{lcm}\left (\lambda\left (p_1^{k_1}\right )\lambda\left (p_2^{k_2}\right )\cdots \lambda\left (p_s^{k_s}\right )\right )$. So Rust's formula is wrong in what regards the prime $2$ (as noticed above).
29.07.2011 15:38
I know, that $s(8)=2$. I write $v_2(n)\le 3$ - it is right.