Kawazoe(@riverplus)さんのCodeIQの問題です。
問題とテストケースはこちらにお世話になりました。解答例もあります。
->https://blog.goo.ne.jp/r-de-r/e/20a11cb53e7dd472a85d8b062cbba191
こちらにも情報があります。
->https://togetter.com/li/1087033

最初方針が見つかりませんでしたが、ヒントに従ってwikipediaを見て、
その定理を使ってすぐ解決しました。
->https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0

p_iをnの素因数とすると　φ(n)=n*(1-1/p_1)*(1-1/p_2)*..(1-1/p_i)*...
n=1*2*3*4*5*6*7*..なので
φ(n)=1*2*3*4*5*6*7*..*(1-1/2)*(1-1/3)*(1-1/5)*(1-1/7)*...
　　=1*2*(1-1/2)*3*(1-1/3)*4*5*(1-1/5)*6*7*(1-1/7)*...
　　=1*(2-1)*(3-1)*4*(5-1)*6*(7-1)*...
よって n=k!の時ret=1 としてφ(n)は
1からkのiに対して、retにもしiが素数ならi-1、素数でないならiを
次々掛けて行った結果のretの値

Juliaには素数かどうか判定するisprimeという関数がありますが
packageのインストールが必要ですので、自前で実装しました。

#julia ver 1.41,1.53,1.10.3

function solve57(n,a)
    function myprime(n)
        for i in 2 : Int(floor(sqrt(n)))
            if ar[i] == 0
                continue
            end    
            for j in i+1 : n
                if mod(j,i) == 0
                    ar[j] = 0
                end    
            end
        end    
    end
  
    ar=ones(Int,n)
    myprime(n)
    m = 1000003 
    ret = 1
    for i in 2 : n
        if ar[i] != 0
            ret = mod(ret*(i-1),m)
        else
            ret = mod(ret*i,m)
        end
    end
    s = a == ret ? "ok " : "no "
    println(s,ret)
end

solve57(10, 829440)
solve57(20, 961998)
solve57(30, 845477)
solve57(100, 145380)
solve57(431, 945906)
solve57(2017, 272985)
solve57(81645, 603326)
solve57(99100, 799614)

Prologでも書きました。
isprimeに相当するものがないようですので、最初に素数のリストを作りました。
配列ですと素数でないものに0を当てていきますが、リストですので、
まだ検討していない数のリストと素数のリストと素数でないリストに分けました。


/*
最初に素数のリストを作る。
リストの素数でないところを0にすると元の値がわからなくなるし、新しいリストを作るのは変わらないので
操作する要素を減らしていった方が良いだろうと思い、まだ検討していない数のリストと素数のリストと素数でないリストに分けた。
nの平方根まで調べればよい
素数でない数はあらかじめ1を引いてからリストに収納すると素数もそれ以外もX1 is mod(X*H,M)で一括できる
appendは非常に遅い。append(L,[X],L1)を繰り返すよりL1=[X|L]を繰り返して最後にreverseした方がダントツに早い
*/
%SWI-Prolog ver 7.42,7.64,9.25
%:-initialization(start).   %ideone,Online Prolog Compiler
%start.

pr1(_,[],L,NPR,L,NPR):-!.      %素数でない数とまだ不明の数のリストに分ける。 Lが不明のリスト
pr1(X,[H|T],L,NPL,LR,NPR):-
  Q is H mod X,(Q ==0->(NPL1=[H|NPL],L1=L);(L1=[H|L],NPL1=NPL)),
  pr1(X,T,L1,NPL1,LR,NPR).

prime57(N,[H|T],PL,NPL,PR,NPR):-  %素数のリストを作る
  H^2>N,!,reverse(PL,L),maplist(plus(-1),[H|T],L1),append(L,L1,PR),reverse(NPL,NPR).
prime57(N,[H|T],PL,NPL,PR,NPR):-    %[H|T]のHは常に素数
  H1 is H-1,PL2=[H1|PL],pr1(H,T,[],NPL,L,NPL1),reverse(L,L1),
  prime57(N,L1,PL2,NPL1,PR,NPR).

totient(R,[],_,R).                       %totient functionを計算
totient(X,[H|T],M,R):-X1 is mod(X*H,M),totient(X1,T,M,R).

solve57(N,M,R):-
  numlist(2,N,L),prime57(N,L,[],[],PL,NPL),totient(1,PL,M,R1),totient(R1,NPL,M,R).

start:-M=1000003,f57(N,A),(solve57(N,M,R)->(R==A->Str=" ok  ";Str=" no  ");
    write(fail)),write(" "),write(Str),writeln(N->R),fail.
start.

f57(10,829440).
f57(20,961998).
f57(30,845477).
f57(100,145380).
f57(431,945906).
f57(2017,272985).
f57(81645,603326).
f57(99100,799614).