OFFSET
1,2
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.
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Art of Problem Solving, 1988 IMO Problems/Problem 6
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.
EXAMPLE
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.
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 *)
PROG
(PARI) a(n)=if(n<5, n, my(r=n, k=n^2-1, t); fordiv(k, p, t=(p+k/p)%n; if(t<r && p>1, if(p+1==n, return(r), r=t)))) \\ Charles R Greathouse IV, Apr 04 2013
(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
CROSSREFS
KEYWORD
easy,nice,nonn
AUTHOR
Rainer Rosenthal, Apr 29 2002
EXTENSIONS
a(17)-a(75) from Charles R Greathouse IV, Apr 04 2013
STATUS
approved