Prove that the Pell’s Equation $x^2 −Dy^2 = 1$ always has a solution where $y$ is a multiple of $41$

Question

$D$ is a positive integer that is not a perfect square

Recently I am taking a introductory number theory course and I met this question right after we learned Pell's equation and Diophantine Approximation. However, I can't see a connection between those 2 topics and this question.

I was trying to assume that $ y = 41k$ where k is an positive integer and substitute it into the equation and I hoped eventually this will simplify to an equation that conforms the form of the Pell's equation which is $x^2-Dy^2=1$. However I did not get any from there.

Also I tried to approach this problem from the Pell's Equation Theorem. Then I found it is impossible to get anything useful from expanding $(x+y{\sqrt D})^k$ plus I cannot determine the smallest solution for it because I don't know the value of D.

Could someone help me on this question? Thank you!

Answer 1

Let $x_n+y_n\sqrt D=(x_1+y_1\sqrt D)^n$ the $n^{\text{th}}$ power of the primitive unit. Since there are only $41^2=1681$ possibilities for $(x_n,y_n)$ $\pmod{41}$ a duplicate must be encountered at some point: $x_n\equiv x_m\pmod{41}$ and $y_n\equiv y_m\pmod{41}$ for some $n>m\ge1$. Then $x_{n-m}=x_nx_m-Dy_ny_m\equiv x_n^2-Dy_n^2\equiv1\pmod{41}$ and $y_{n-m}=-x_ny_m+y_nx_m\equiv-x_ny_n+y_nx_n\equiv0\pmod{41}$.

EDIT: As an example let $D=3$ and the first solution to Pell's equation is $x_1+y_1\sqrt D=2+1\sqrt3$. Now let's make a table of values $\pmod{41}$: $$\begin{array}{r|r|r}n&x_n&y_n\\\hline 1&2&1\\ 2&7&4\\ 3&26&15\\ 4&15&15\\ 5&34&4\\ 6&39&1\\ 7&40&0\\ 8&39&40\\ 9&34&37\\ 10&15&26\\ 11&26&26\\ 12&7&37\\ 13&2&40\\ 14&1&0\\ 15&2&1\end{array}$$ For example $(2+1\sqrt3)^2=7+4\sqrt3$, $(2+1\sqrt3)^3=26+15\sqrt3$, and $(2+1\sqrt3)^4=97+56\sqrt3$ so $x_4=97\equiv15\pmod{41}$ and $y_4=56\equiv15\pmod{41}$, thus explaining the row $n=4$, $x_n\equiv15$, $y_n\equiv15$. The first duplicate was $x_{15}\equiv x_1\equiv2\pmod{41}$ and $y_{15}\equiv y_1\equiv1\pmod{41}$, so that tells us that $x_{15-1}=x_{14}\equiv1\pmod{41}$ and $y_{15-1}=y_{14}\equiv0\pmod{41}$. Perhaps a bit anticlimactic since we already found $2$ solutions on our way to generating the first duplicate. Indeed $x_{14}^2-3y_{14}^2=50843527^2-3\cdot29354524^2=1$ and $y_{14}=29354524=41\cdot715964$.

EDIT: Oh yeah, the last $2$ lines: since $(x_n+y_n\sqrt D)(x_n-y_n\sqrt D)=(x_1+y_1\sqrt D)^n(x_1-y_1\sqrt D)^n=(x_1^2-Dy_1^2)^n=(1)^n=1$ we see that $(x_n+y_n\sqrt D)^{-1}=(x_n-y_n\sqrt D)$ so $(x_{n-m}+y_{n-m}\sqrt D)=(x_n+y_n\sqrt D)(x_m-y_m\sqrt D)=(x_nx_m-Dy_ny_m)+(-x_ny_m+y_nx_m)\sqrt D$

EDIT My program that finds the fundamental solution to $x^2-Dy^2=1$ and the first power $n-m$ for which $x_{n-m}\equiv1\pmod{41}$ and $y_{n-m}\equiv0\pmod{41}$

program pell
   use ISO_FORTRAN_ENV
   implicit none
   integer(INT64) D
   integer(INT64) sqD, r, s, a, p0, p1, p, q0, q1, q, n
   integer(INT64) m
   write(*,'(a)') '  D         x_1                  y_1            n-m'
   do D = 1, 100
      sqD = int(sqrt(D+0.5D0),INT64)
      if(sqD**2==D) cycle
      r = 0
      s = 1
      p0 = 0
      p1 = 1
      q0 = 1
      q1 = 0
      do n = 1, 200
         a = (sqD+r)/s
         p = a*p1+p0
         p0 = p1
         p1 = p
         q = a*q1+q0
         q0 = q1
         q1 = q
         r = a*s-r
         s = (D-r**2)/s
         if(mod(n,2) == 0 .AND. s == 1) then
            write(*,'(i4,1x,i17,1x,i18)',advance='no') D,p,q
            p0 = mod(p,41)
            q0 = mod(q,41)
            p1 = 1
            q1 = 0
            do m = 1, 1000000
               p = p1*p0+D*q1*q0
               q = p1*q0+q1*p0
               p1 = mod(p,41)
               q1 = mod(q,41)
               if(p1 == 1 .AND. q1 ==0) then
                  write(*,'(1x,i4)') m
                  exit
               end if
            end do
            exit
         end if
      end do
   end do
end program pell

And its output:

  D         x_1                  y_1            n-m
   2                 3                  2    5
   3                 2                  1   14
   5                 9                  4   20
   6                 5                  2   42
   7                 8                  3   21
   8                 3                  1    5
  10                19                  6   20
  11                10                  3   42
  12                 7                  2    7
  13               649                180   14
  14                15                  4    7
  15                 4                  1   21
  17                33                  8   42
  18                17                  4    5
  19               170                 39   42
  20                 9                  2   20
  21                55                 12   40
  22               197                 42   42
  23                24                  5   10
  24                 5                  1   42
  26                51                 10   42
  27                26                  5   14
  28               127                 24   21
  29              9801               1820   14
  30                11                  2   42
  31              1520                273    5
  32                17                  3    5
  33                23                  4   40
  34                35                  6   21
  35                 6                  1   42
  37                73                 12   20
  38                37                  6   42
  39                25                  4   40
  40                19                  3   20
  41              2049                320   82
  42                13                  2   40
  43              3482                531   10
  44               199                 30   21
  45               161                 24   10
  46             24335               3588   20
  47                48                  7    7
  48                 7                  1    7
  50                99                 14    5
  51                50                  7   20
  52               649                 90   14
  53             66249               9100   14
  54               485                 66   14
  55                89                 12    7
  56                15                  2    7
  57               151                 20   40
  58             19603               2574   42
  59               530                 69   10
  60                31                  4   21
  61        1766319049          226153980    5
  62                63                  8   20
  63                 8                  1   21
  65               129                 16   42
  66                65                  8   10
  67             48842               5967   42
  68                33                  4   42
  69              7775                936   14
  70               251                 30   42
  71              3480                413   21
  72                17                  2    5
  73           2281249             267000   20
  74              3699                430   20
  75                26                  3   14
  76             57799               6630   21
  77               351                 40   40
  78                53                  6    8
  79                80                  9    7
  80                 9                  1   20
  82               163                 18   82
  83                82                  9    4
  84                55                  6   40
  85            285769              30996    2
  86             10405               1122   20
  87                28                  3   40
  88               197                 21   42
  89            500001              53000   42
  90                19                  2   20
  91              1574                165   40
  92              1151                120    5
  93             12151               1260    7
  94           2143295             221064    3
  95                39                  4    7
  96                49                  5   21
  97          62809633            6377352   42
  98                99                 10    5
  99                10                  1   42