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,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

Cf. A027750, A005563.

Sequence in context: A066262 A195989 A174715 * A071439 A100941 A082119

Adjacent sequences: A069814 A069815 A069816 * A069818 A069819 A069820

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