APL(NARS), 21 chars

{⌊⍵÷⍨1+×/k/⍨1=⍵∨k←⍳⍵}

Even if do not follow the precise definition in the question it seems it would be ok until 1000 at last if used rational "x" numbers for bignums.

test:

  g←{⌊⍵÷⍨1+×/k/⍨1=⍵∨k←⍳⍵}
  {⍵,g¨⍵}¨⍳8
1 2  2 1  3 1  4 1  5 5  6 1  7 103  8 13 
  {⍵,g¨⍵}¨9..14
9 249  10 19  11 329891  12 32  13 36846277  14 1379 
  {⍵,g¨⍵}¨15..20
15 59793  16 126689  17 1230752346353  18 4727  19 336967037143579  20 436486 
  {⍵,g¨⍵}¨21..25
21 2252263619  22 56815333  23 4.886959686E19  24 1549256  25 1.654529071E18 
  {⍵,g¨⍵}¨21..25x
21 2252263619  22 56815333  23 48869596859895986087  24 1549256  25 1654529071288638505 
  f←{e←¯1*1∊⍵∣×⍨¯2↓1↓k←⍳⍵⋄⍵÷⍨e+×/k/⍨1=⍵∨k}
  kkk/⍨{(g ⍵)≠f ⍵}¨kkk←⍳1000x

TI-BASIC (TI-84 Plus CE Python), 30 bytes

Input N
1+prod(seq(K^(1=gcd(K,N)),K,1,N
int(Ans/N

translation of H.Pwiz's answer in Husk

JavaScript (ES6), 83 81 80 78 76 68 bytes

My first pass at this was a few bytes longer than Neil's solution, which is why I originally ditched it in favour of the array reduction solution below. I've since golfed it down to tie with Neil.

n=>(g=s=>--x?g(s*(h=(y,z)=>z?h(z,y%z):--y?1:x)(n,x)):++s)(1,x=n)/n|0

Try it

o.innerText=(f=
n=>(g=s=>--x?g(s*(h=(y,z)=>z?h(z,y%z):--y?1:x)(n,x)):++s)(1,x=n)/n|0
)(i.value=8);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>

Non-recursive, 76 bytes

I wanted to give a non-recursive solution a try to see how it would turn out - not as bad as I expected.

n=>-~[...Array(x=n)].reduce(s=>s*(g=(y,z)=>z?g(z,y%z):y<2?x:1)(--x,n),1)/n|0

Try it

o.innerText=(f=
n=>-~[...Array(x=n)].reduce(s=>s*(g=(y,z)=>z?g(z,y%z):y<2?x:1)(--x,n),1)/n|0
)(i.value=8);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>

Haskell, 42 bytes

f n=div(product[x|x<-[1..n],gcd x n<2]+1)n

Try it online!

Uses the integer division trick as all the other answers.
Uses 1-based indices.

Explanation

f n=                                       -- function
    div                                  n -- integer division of next arg by n
       (product                            -- multiply all entries in the following list
               [x|                         -- return all x with ...
                  x<-[1..n],               -- ... 1 <= x <= n and ...
                            gcd x n<2]     -- ... gcd(x,n)==1
                                      +1)  -- fix e=1

JavaScript (ES6), 72 70 68 bytes

f=(n,p=1,i=n,a=n,b=i)=>i?f(n,b|a-1?p:p*i,i-=!b,b||n,b?a%b:i):-~p/n|0

<input type=number min=1 oninput=o.textContent=f(+this.value)><pre id=o>

Integer division strikes again. Edit: Saved 2 bytes thanks to @Shaggy. Saved a further 2 bytes by making it much more recursive, so it may fail for smaller values than it used to.

Pari/GP, 36 bytes

n->(prod(i=1,n,i^(gcd(i,n)==1))+1)\n

Try it online!

Axiom, 121 bytes

f(n)==(e:=p:=1;for i in 1..n repeat(if gcd(i,n)=1 then p:=p*i;e=1 and i>1 and i<n-1 and(i*i)rem n=1=>(e:=-1));(p+e)quo n)

add some type, ungolf that and result

w(n:PI):PI==
   e:INT:=p:=1
   for i in 1..n repeat
       if gcd(i,n)=1 then p:=p*i
       e=1 and i>1 and i<n-1 and (i*i)rem n=1=>(e:=-1)
   (p+e)quo n

(5) -> [[i,f(i)] for i in 1..25]
   (5)
   [[1,2], [2,1], [3,1], [4,1], [5,5], [6,1], [7,103], [8,13], [9,249],
    [10,19], [11,329891], [12,32], [13,36846277], [14,1379], [15,59793],
    [16,126689], [17,1230752346353], [18,4727], [19,336967037143579],
    [20,436486], [21,2252263619], [22,56815333], [23,48869596859895986087],
    [24,1549256], [25,1654529071288638505]]
                                                  Type: List List Integer

(8) -> f 101
   (8)
  9240219350885559671455370183788782226803561214295210046395342959922534652795_
   041149400144948134308741213237417903685520618929228803649900990099009900990_
   09901
                                                    Type: PositiveInteger

R, 82 bytes

function(n)(prod((1:n)[g(n,1:n)<2])+1)%/%n
g=function(a,b)ifelse(o<-a%%b,g(b,o),b)

Uses integer division rather than figuring out e like many answers here, although I did work out that e=2*any((1:n)^2%%n==1%%n)-1 including the edge case of n=1 which I thought was pretty neat.

Uses rturnbull's vectorized GCD function.

Try it online!

Jelly, 8 7 bytes

1 byte thanks to Dennis.

gRỊTP‘:

Try it online!

You don't really have to compute e since you need to divide anyway.

Japt, 11 bytes

õ fjU ×Ä zU

Try it

Explanation

Implicit input of integer U.

õ

Generate an array of integers from 1 to U.

fjU

Filter (f) co-primes of U.

×

Reduce by multiplication.

Ä

Add 1.

zU

Divide by U, floor the result and implicitly output.

05AB1E, 8 bytes

Lʒ¿}P>I÷

Try it online!

J, 33 bytes

3 :'<.%&y>:*/(#~1&=@(+.&y))1+i.y'

This one is more of a request to see an improvement than anything else. I tried a tacit solution first, but it was longer than this.

explanation

This is fairly straightforward translation of Mr. Xcoder's solution into J.

Try it online!

Python 2, 62 bytes

n=input();k=r=1
exec'r*=k/n*k%n!=1or k/n;k+=1;'*n*n
print-~r/n

Try it online!

Pyth, 11 bytes

/h*Ff>2iTQS

Try it here!

How?

• /h*Ff>2iTQS - Full program.

• S - Generate the inclusive range [1, input]

• f - Filter-keep those:

  • iTQ - whose GCD with the input.

  • >2 - Is less than two (can be replaced by either of the following: q1, !t)

• *F - Apply multiplication repeatedly. In other words, the product of the list.

• h - Increment the product by 1.

• / - Floor division with the input.

TL;DR: Get all the coprimes to the input in the range [1, input], get their product, increment it and divide it by the input.

Mathematica, 91 bytes

If[(k=#)==1,2,(Times@@Select[Range@k,CoprimeQ[k,#]&]+If[IntegerQ@PrimitiveRoot@#,1,-1])/#]&

Husk, 11 bytes

S÷ȯ→Π§foε⌋ḣ

Try it online!

Explanation

          ḣ   Range from 1 to input
     §foε⌋    Keep only those whose gcd with the input is 1
    Π         Product
  ȯ→          Plus 1
S÷            Integer division with input