This was inspired by the Archimedes Cattle Problem. A crucial step is to solve the Pell equation,
$$u^2-(609)(7766)v^2=1\tag1$$
and whose fundamental solution is,
$$\big(300426607914281713365\sqrt{609} + 84129507677858393258\sqrt{7766}\big)^2=u+\sqrt{(609)(7766)}\,v$$
Of course, there are an infinite number of $u,v$ that solve $(1)$. However, the complete solution to the problem desires that $v=9314y$, or the Pell equation,
$$x^2-(609)(7766)(9314^2)y^2=1\tag2$$
which has fundamental solution,
$$\big(u+\sqrt{(609)(7766)}\,v\big)^{\color{brown}{2329}} = x+\sqrt{(609)(7766)}\,\color{blue}{9314}\,y$$
Note that $4\times\color{brown}{2329} - 2 = \color{blue}{9314}$.
Questions:
In general, given the fundamental solution to, $$u^2-dv^2=1$$ how do we find integer $n$ such that, $$(u+\sqrt{d}\,v)^n = x+\sqrt{d}\,y$$ and $y$ is integrally divisible by some desired integer $p$? In other words, can we express $n$ as a function in terms of $p$? (If the general case is too complicated, then assume $d,p$ to be primes.)
From a limited computer search, I observed that minimum $n\leq p$. Is this indeed true?
Example:
Given the expansion of,
$$\big(649 + 180\sqrt{13}\big)^n = x+y\sqrt{13}$$
then the smallest $n$ such that $\displaystyle\frac{y}{p}$ is an integer are the following,
$$\begin{array}{|c|c|c|c|c|c|} \hline p&n& & &p&n\\ \hline \color{green}2&1& & &\color{blue}{19}&10\\ \color{green}3&1& & &\color{red}{23}&11\\ \color{green}5&1& & &\color{red}{29}&7\\ \color{blue}7&4& & &\color{blue}{31}&16\\ \color{blue}{11}&2& & &\color{blue}{37}&19\\ \color{green}{13}&13& & &\color{blue}{41}&7\\ \color{red}{17}&4& & &\color{red}{43}&7\\ \hline \end{array}$$
For example, let $p=\color{blue}7$, so $\big(649 + 180\sqrt{13}\big)^4 = 1419278889601 + \color{blue}7\times56233877040\sqrt{13}$.
Edit: Per Batominovski's answer, primes in either blue, green, red have $p+1,\;p,\;p-1$ divisible by $n$, respectively.
Define $u_r+\sqrt{d}v_r:=\left(u+\sqrt{d}v\right)^r$, where $u_r,v_r\in\mathbb{Z}$ and $r\in\mathbb{N}_0$. Then, you can see that $v_{r+2}+av_{r+1}+bv_r=0$ for some $a,b\in\mathbb{Z}$ and for all $r\in\mathbb{N}_0$ (with $v_0=0$ and $v_1=v$). Indeed, $a=-2u$ and $b=1$. If $p$ is a prime natural number, then either $t^2+at+b\in\mathbb{F}_p[t]$ is reducible or $t^2+at+b$ factors into linear terms over $\mathbb{F}_{p^2}$.
If $t^2+at+b$ with $b\neq 0$ in $\mathbb{F}_p$ is reducible over $\mathbb{F}_p$ with simple roots, then it follows easily that $v_{p-1}=v_0=0$ in $\mathbb{F}_p$, so we can take $n=p-1$. The minimum of such $n$'s is a divisor of $p-1$.
If $t^2+at+b$ with $b\neq 0$ in $\mathbb{F}_p$ is a perfect square in $\mathbb{F}_p[t]$, then we have $v_p=v_0=0$, so we can take $n=p$. The minimum of such $n$'s is either $1$ or $p$.
Now, suppose that $t^2+at+b$ is irreducible over $\mathbb{F}_p$. Then, the roots of $t^2+at+b$ in $\mathbb{F}_{p^2}$ are $\alpha,\beta\in\mathbb{F}_{p^2}$ satisfying $\alpha^p=\beta$ and $\beta^p=\alpha$. Since $v_r=\kappa\left(\alpha^r-\beta^r\right)$ for some $\kappa\in\mathbb{F}_{p^2}$ and for all $r\in\mathbb{N}_0$, it follows that $v_{p+1}=v_0=0$, so we may take $n=p+1$. The minimum of such $n$'s must divide $p+1$.
Suppose that $p$ is an odd prime. Of course, $n$ can be taken to be $\frac{p- 1}{2}$ in Case 1 and $\frac{p+1}{2}$ in Case 3 (or the smallest of such $n$'s must divide $\frac{p-1}{2}$ in Case 1 or $\frac{p+1}{2}$ in Case 3). If $\alpha$ and $\beta$ are the roots of $t^2+at+b$ in $\mathbb{F}_p$ or $\mathbb{F}_{p^2}$, then $\beta=\frac{1}{\alpha}$ (this argument works only when $b=1$ in $\mathbb{F}_p$, which holds in your problem). Note that either $\alpha^{p-1}=1$ (if $\alpha\in\mathbb{F}_p$) or $\alpha^{p+1}=1$ (if $\alpha\in\mathbb{F}_{p^2}\setminus\mathbb{F}_p$, where we have $\alpha^p=\beta=\frac{1}{\alpha}$). Since $v_r=\kappa\left(\alpha^r-\beta^r\right)=\frac{\kappa}{\alpha^r}\left(\alpha^{2r}-1\right)$ for some $\kappa$ in $\mathbb{F}_p$ or $\mathbb{F}_{p^2}$ and for all $r\in\mathbb{N}_0$, we conclude that $v_{\frac{p-1}{2}}=v_0=0$ in Case 1 and $v_{\frac{p+1}{2}}=v_0=0$ in Case 3.
In this particular problem, $a=0$ and $b=1$ in $\mathbb{F}_2$, so $p=2$ falls into Case 2 always. More generally, a prime $p$ falls into Case 2 if and only if $p$ divides $2dv$. If $p$ divides $v$, then $n$ can be taken to be $1$. If $p$ divides $2d$ but not $v$, then $n=p$ is the smallest of such $n$'s.
P.S.: While the case $b=0$ in $\mathbb{F}_p$ doesn't happen in your particular problem, it is worth noting that there may not exist $n\in\mathbb{N}$ such that $v_n=v_0=0$ in $\mathbb{F}_p$ if $p$ divides $b$.
It is also not difficult to show that, if $p=p_1^{k_1}p_2^{k_2}\cdots p_l^{k_l}$, where $p_1,p_2,\ldots,p_l$ are pairwise distinct prime natural numbers and $k_1,k_2,\ldots,k_l$ are nonnegative integers, then the smallest $n$ satisfies $n\leq p$. In fact, we have a stronger bound for this $n$: $$n\leq \prod_{p_i \mid 2dv}\,p_i^{k_i} \,\prod_{p_i \nmid 2dv}\,\left(\frac{p_i+1}{2}\right)p_i^{k_i-1}\,.$$ We have even a better bound: the smallest $n$ must divide $$\text{lcm}\left(L_1,L_2,L_3\right) \mid \prod_{p_i \mid 2dv}\,p_i^{k_i} \,\prod_{p_i \text{ in Case 1}}\,\left(\frac{p_i-1}{2}\right)p_i^{k_i-1}\,\,\prod_{p_i \text{ in Case 3}}\,\left(\frac{p_i+1}{2}\right)p_i^{k_i-1}\,,$$ where $L_1$ is the least common multiple of $\left(\frac{p_i-1}{2}\right)p_i^{k_i-1}$ for $p_i$ in Case 1, $L_2:=\prod_{p_i \mid 2dv}\,p_i^{k_i}$, and $L_3$ is the least common multipleof $\left(\frac{p_i+1}{2}\right)p_i^{k_i-1}$ for $p_i$ in Case 3. Yet still a better bound exists: if $n_i$ is the smallest positive integer such that $p_i$ divides $v_{n_i}$, then the minimum value of $n$ is a factor of $$\text{lcm}\left(n_1p_1^{k_1-1},n_2p_2^{k_2-1},\ldots,n_lp_l^{k_l-1}\right)\mid\prod_{i=1}^l\,n_ip_i^{k_i-1}\,.$$ For example, with $d:=13$ and $p:=7^2\cdot 29$, we can take $n$ to be $\text{lcm}(4\cdot7,7)=28$ (which is also the smallest value of all such $n$'s).