A280990 Least prime p such that n divides phi(p*n).

2, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 3, 13, 7, 31, 2, 17, 3, 19, 5, 7, 11, 23, 3, 5, 13, 3, 7, 29, 31, 31, 2, 67, 17, 71, 3, 37, 19, 13, 5, 41, 7, 43, 11, 31, 23, 47, 3, 7, 5, 103, 13, 53, 3, 11, 7, 19, 29, 59, 31, 61, 31, 7, 2, 131, 67, 67, 17, 139, 71, 71, 3, 73, 37, 31, 19, 463

Offset: 1

Author

Altug Alkan, Jan 12 2017

Keywords

• nonn

Comments

n*a(n) are 2, 4, 9, 8, 25, 18, 49, 16, 27, 50, 121, 36, 169, 98, 465, 32, 289, ...

a(n) <= A034694(A007947(n)). If n is in A050384 then a(n) = A034694(n). - Robert Israel, Jan 12 2017

Examples

			a(15) = 31 because 15 does not divide phi(p*15) for p < 31 where p is prime and phi(31*15) = 2*4*30 is divisible by 15.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A000010, A007694, A007947, A034694, A050384, A109395.

Cf. A000079, A065119, A086761: for those n such that a(n)=2,3,5. - Michel Marcus, Jan 20 2017

Programs

Maple

f:= proc(n) local p;
    p:= 2;
    while numtheory:-phi(p*n) mod n <> 0 do p:= nextprime(p) od:
    p
end proc:
map(f, [$1..100]); # Robert Israel, Jan 12 2017

Mathematica

lpp[n_]:=Module[{p=2},While[Mod[EulerPhi[p*n],n]!=0,p=NextPrime[p]];p]; Array[lpp,80] (* Harvey P. Dale, Sep 26 2020 *)

PARI

a(n)=my(k = 1); while (eulerphi(prime(k)*n) % n != 0, k++); prime(k);

PARI

a(n)=my(t=n/gcd(eulerphi(n),n)); if(t==1, return(2)); forstep(p=if(t%2,2*t,t)+1, if(isprime(t), t, oo),lcm(t,2), if(isprime(p), return(p))); t \\ Charles R Greathouse IV, Jan 20 2017

Formula

a(p^k) = p for all primes p and k >= 1. - Robert Israel, Jan 12 2017

a(n) << n^5 by Xylouris' improvement to Linnik's theorem. - Charles R Greathouse IV, Jan 20 2017