The Congruential Approach

The Linear System at Hand

n = 40;
b = Table[0, {n}]; 
    b[[1]] = 1;
A = SparseArray[{{i_, i_} -> Prime[i]}, 
                n] + (# + Transpose[#]) &@
          SparseArray[
            Flatten@Table[{i, i + (2^j)} -> 1, {i, n - 1}, {j, 0, 
                  Log[2. , n - i]}], n];

Cramer's Rule

x1[A_] := 
        Determinant[Take[A, {2, -1}, {2, -1}]]/
          Determinant[A];

The Chinese Remaindering

Needs["NumberTheory`NumberTheoryFunctions`"];
WorkPrimes[A_] := 
        Module[{HadamardBound = Product[A[[i, i]], {i, Length@A}], 
            work = {}, prod = 1, k = PrimePi[(2^30)] + 1}, 
          While[prod < HadamardBound, work = {work, p = Prime[k++]}; 
            prod *= p]; Flatten@work];
Determinant[A_] := 
        Module[{primeList = WorkPrimes[A], detList}, 
          detList = Determinant[A, Modulus ->  #] & /@ primeList; 
          ChineseRemainder[detList, primeList]];

Wiedemann's Randomized Algorithm for Modular Determinants

Determinant[A_, 
          opts___Rule] := (m = Modulus /. opts; 
          Module[{n = Length@A}, 
            Mod[(((-1))^n) First@MinPol[A, n], m]]);
MinPol[A_, minDegree_] := 
        Module[{n = Length@A, pol = {}, u, v, b}, 
          While[Length@pol ≤ minDegree, {u, v} = 
              Table[Random[Integer, {0, m - 1}], {2}, {n}]; 
            a = Mod[NestList[u . (b = Mod[A . b, m]) &, u . (b = v), 
                  2 n - 1], m]; pol = LinearRecurrence[a, n]]; 
          pol];

Berlekamp-Massey algorithm as given in [KS91,p. 31]

LinearRecurrence[a_, d_] := 
        Module[{Λ = {1}, Σ = {}, 
            l = 0, δ = 1, r, δr, Λ1}, 
          For[r = 1, r ≤ 2 d, r++, 
            PrependTo[Σ, 0]; δr = 
              Take[a, {r, 
                    r - Length@Λ + 
                      1, -1}] . Λ; 
            If[(δr = Mod[δr, m]) > 0, Λ1 = 
                PadRight[Λ, 
                    Length@Σ] - δr × Σ/δ; 
              If[2 l < r, 
                l = r - 
                    l; δ = δr; Σ = Λ]; Λ = PolynomialMod[Λ1, m]]]; 
          Reverse@Λ];

The Solution

sol1 = x1[A]