Note that b = A001177 has the following properties:
  (1) b(mn) = lcm(b(m), b(n)) if gcd(m, n) = 1, so b(mn)/mn <= (b(m)/m)*(b(n)/n);
  (2) For a prime p, b(p) divides p-Legendre(p,5);
  (3) For a prime p, b(p^e) = p^t*b(p) for some t, where t <= e-1.
Here A001177(k) = k-1, so gcd(A001177(k), k) = 1, so k must not be divisible by 5.
  (a) k must be squarefree. Otherwise suppose p^e divides k while p^(e+1) does not, e >= 2. If b(p^e) >= p*b(p) then gcd(A001177(k), k) >= p, a contradiction; if b(p^e) = b(p) then b(k)/k <= b(p^e)/p^e <= (p+1)/p^e <= 3/4, k <= 4, impossible;
  (b) If k is odd, let k = Product_{i=1..r} p_i where b(p_i) <= ((p_i)+1)/2 for i = 1..s and b(p_i) = (p_i)+-1 for i=s+1..r, then b(k)/k <= (Product_{i=1..s} ((p_i)+1)/(2*(p_i))) * lcm(b(p_(s+1)), ..., b(r))/(Product_{i=s+1..r} p_i). Since that lcm(b(p_(s+1)), ..., b(r)) <= 2*(Product_{i=s+1..r} b(i)/2) = 2*(Product_{i=s+1..r} ((p_i)+1)/2), we have b(k)/k <= 2*(Product_{i=1..r} ((p_i)+1)/(2*(p_i))). If r >= 2, then b(k)/k <= 2*(4/6)*(8/14) = 16/21, so k <= 4, impossible;
  (c) If k is even, by b(2) = 3 we have 3 divides k-1, so 3 does not divide k. Let k = 2*(Product_{i=1..r} p_i), p_i > 3, we have b(k)/k <= 3*(Product_{i=1..r} ((p_i)+1)/(2*(p_i))). If r >= 2, then b(k)/k <= 3*(8/14)*(12/22) = 72/77, so k <= 15, impossible;
For an odd prime p we have b(p) = (p+-1)/r for some r and b(2p) = (3/2)*(p+-1)/r for some r. It is easy to see that if b(k) = k-1 then k must be prime.