A069817 Smallest remainder of p+q modulo n, where p*q = n^2 - 1, 1 < p < n-1, or n if no such factorization exists.

1, 2, 3, 4, 1, 6, 2, 0, 3, 6, 1, 12, 3, 2, 0, 8, 2, 18, 1, 4, 0, 10, 2, 0, 5, 6, 3, 12, 1, 30, 2, 8, 12, 2, 0, 12, 7, 10, 3, 16, 1, 42, 3, 4, 15, 14, 2, 0, 2, 14, 3, 20, 3, 6, 0, 0, 15, 22, 4, 60, 11, 2, 0, 8, 5, 18, 5, 20, 3, 26, 1, 72, 13, 10, 15

Offset: 1

Author

Rainer Rosenthal, Apr 29 2002

Keywords

• easy
• nice
• nonn

Comments

Factoring n^2-k = p*q for k > 1 gives p+q never divisible by k*a. The remainders p+q mod k*a have minimum > 0 for k > 1. This sequence shows the minimum for k=1, where there are zero values, e.g. a(8)=0. The restriction 1 < p < n-1 is due to the fact that (n-1)(n+1) = n^2-1 and (n-1)+(n+1)=2n is zero mod n. Excluding this trivial case as well as 1*(n^2-1) with 1+(n^2-1)=n^2=0 (mod n) gives the more interesting elements.

Examples

			a(7)=2 since 7^2-1 = 48 = 2*24 = 3*16 = 4*12 where the sums of the factors (mod 7) are: [2+24]=5, [3+16]=5, [4+12]=2.
		

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Art of Problem Solving, 1988 IMO Problems/Problem 6

Crossrefs

Cf. A027750, A005563.

Programs

Haskell

a069817 1 = 1
a069817 n = if null ms then n else minimum $ map (`mod` n) ms
   where ms = zipWith (+) ds $ map (div n') ds
         ds = takeWhile (< n - 1) $ tail $ a027750_row n'
         n' = n ^ 2 - 1
-- Reinhard Zumkeller, May 16 2013

Mathematica

a[n_] := (r = Reduce[1 < p < n - 1 && n^2 - 1 == p*q, {p, q}, Integers]; factors = If[r === False, n, {p, q} /. {ToRules[r]}]; Mod[#[[1]] + #[[2]], n] & /@ factors // Min); Table[ a[n] , {n, 1, 16}] (* Jean-François Alcover, Apr 04 2013 *)

PARI

a(n)=if(n<5,n,my(r=n,k=n^2-1,t); fordiv(k,p,t=(p+k/p)%n;if(t1, if(p+1==n,return(r),r=t)))) \\ Charles R Greathouse IV, Apr 04 2013

Formula

If n-1 and n+1 are prime then set a(n) = n. Otherwise check (p+q mod n) for all natural numbers p, q which satisfy: p*q = n^2-1 and 1 < p < n-1 and 1 < q < n-1.

Extensions

a(17)-a(75) from Charles R Greathouse IV, Apr 04 2013