A248058 Least positive integer m such that m*n divides phi(m^2+n^2), where phi(.) is Euler's totient function.

1, 1, 2, 1, 4, 1, 8, 1, 10, 1, 726, 2, 12, 1, 4, 1, 18, 3, 20, 1, 96, 23, 22, 1, 24, 1, 72, 2, 30, 8, 30, 1, 32, 35, 34, 1, 222, 40, 26, 1, 1312, 43, 42, 46, 360, 44, 48, 2, 588, 1, 50, 2, 5100, 1, 88, 1, 19152, 60, 8, 16

Offset: 1

Author

Zhi-Wei Sun, Sep 30 2014

Keywords

• nonn

Comments

Conjecture: (i) a(n) exists for any n > 0.

(ii) For each n > 0, there is a positive integer m such that m*n divides sigma(m^2+n^2), where sigma(k) is the sum of all positive divisors of k.

Note that a(n) = 1 if n^2 + 1 is prime. When n^2 + (n+1)^2 is prime, n*(n+1) divides phi(n^2 + (n+1)^2) = n^2 + (n+1)^2 - 1 and hence a(n) <= n + 1.

If (n*q)^2 + 1 is prime for some q > 0, then for m = n^2*q the number phi(m^2+n^2) = phi(n^2)*phi((n*q)^2+1) = phi(n^2)*n^2 *q^2 is divisible by m*n = n^3*q. - Zhi-Wei Sun, Oct 03 2014

Examples

			a(5) = 4 since 4*5 divides phi(4^2 + 5^2) = phi(41) = 40.
a(919) = 37160684 since the product 919*37160684 = 34150668596 divides phi(919^2 + 37160684^2) = phi(1380916436192417) = 1379413805929632 = 40392*34150668596.
		

Links

• Zhi-Wei Sun, Table of n, a(n) for n = 1..1242

Crossrefs

Cf. A000010, A000203, A248035, A248036, A248054.

Programs

Mathematica

Do[m=1;Label[aa];If[Mod[EulerPhi[m^2+n^2],m*n]==0,Print[n," ",m];Goto[bb]];m=m+1;Goto[aa];Label[bb];Continue,{n,1,60}]

PARI

a(n)=m=1;while(eulerphi(m^2+n^2)%(m*n),m++);m
vector(100,n,a(n)) \\ Derek Orr, Oct 01 2014