There are finit solutions: $(n,m)=(1,1),(1,2),(1,4),(2,1),(2,7),(4,1),(5,28),$ $(n,m)=(7,2),(10,103),(11,62),(13,4),(13,43),$ $(n,m)=(16,37),(20,13),(23,38),(37,49).$

emregirgin35 wrote: Find all pairs of positive odd integers $(m,n)$ such that $n | 3m+1$ and $m | n^2+3$ Some of your solutions does not hold this condition actually. I think, you have all the solutions regardless of that condition.

He cannot have all solutions. Nowhere is it specified $m,n$ must be positive, and $(m,n) = (-1,-1)$ is obviously a solution.

mavropnevma wrote: He cannot have all solutions. Nowhere is it specified $m,n$ must be positive, and $(m,n) = (-1,-1)$ is obviously a solution. Edited!

answer: $(m,n)\in (1,1), (43,13), (49,37)$. There are three cases: 1) $m=n$; in the case $m=n=1$. 2) $m<n$; $2n=3m+1$ - no solution. 3) $m>n$; easily get $m>n>9$ and $nm=n^2+9m+3$, $ (m,n)\in (43,13),(49,37) $.

I found all positive integer solutions. Solution. Obviosly $(n,3)=1,(m,3)=1$ and $mn|n^2+3+9m$. If $(mn,3)=1$ and $mn|n^2+3+9m$, then $n|1+3m$ and $m|n^2+3$ - solution. Let $n^2+3+9m=kmn$ or $m=\frac{n^2+3}{kn-9}$. Let $3m+1=ln$, then $n+3l=km$ or $3l,n$ are roots of $x^2-kmx+3+9m=0$ with $D=k^2m^2-12(3m+1)=(km-y)^2$. We can found solutions for small n. I found for $n\le 13$. For $n>13$ k=1. It give $m=\frac{n^2+3}{n-9}=n+9+3\frac{28}{n-9}$. Note that $(n,3)=1$, therefore $n-9|28$.

A solution with lots of case checking. Let $3m+1=nk .\Rightarrow m| \frac{(3m+1)^2}{k^2}+1 \Rightarrow m|k^2+1$ . If $n \ge k \Rightarrow 3m+1 \ge k^2 \Rightarrow k^2+1=m,2m ,3m$,or $4m$ .Considering all the cases If $k^2+1 = m \Rightarrow k|4 \Rightarrow k=1,2,4$ .substituting we can find the solutions . similarly we can analyze $k=2m ,3m,4m$ If $k \ge n \Rightarrow 3m+1 \ge n^2 \Rightarrow n^2+3=m,2m,3m$ or $4m$ ,Which can be analyzed as previous.

I have another solution. Let $3m+1=nk$, $k$ is even. We get : \[\dfrac{nk-1}{3}\mid n^2+3\Rightarrow nk-1\mid 3n^2k+9k\Rightarrow nk-1\mid 9k+3n\] Deduce : \[nk-1\leq 9k+3n\Leftrightarrow (n-9)(k-3)\leq 28\] If $k=2$, we don't find out $(m,n)$ satisfy the prolem. If $k=4$, we have : \[4n-1\mid 36+3n\Rightarrow 4n-1\mid 147\Rightarrow n\in \left \{ 1,37 \right \}\] Consider $k \geq 6$. \[n-9\leq \dfrac{28}{k-3}\leq \dfrac{28}{3}\Rightarrow n\leq 18\] Since $n$ is odd, $n\in \left \{ 1,3,5,7,9,11,13,15,17 \right \}$. Solution : \[(m,n)=(1,1),(43,13),(49,37)\]

Note that $3m+1$ and $n^2+3$ are even numbers(the later being divisible by $4$) since $m,n$ are odd.So the conditions can be extended to $2n|3m+1$ and $4m|n^2+3$ Now assume that $\frac{3m+1}{2n} \ge 3$ and $\frac{n^2+3}{4m} \ge 3$. This means that $3m+1 \ge 6n$ and $n^2+3 \ge 12m$ Also the problem conditions imply that $mn|(3m+1)(n^2+3) \implies mn|n^2+9m+3$ Thus $\frac{6n-1}{3}n \le mn \le n^2+9m+3 \le n^2+9\frac{n^2+3}{12}+3 \implies 3n^2-4n-63 \le 0 \implies n \le 5$ Now case studies with $n=1,3,5$ gives us the only solution $(m,n)=(1,1)$ Now we check the rest of the cases: Case 1: $3m+1=2n$ In this case we have $m|n^2+3 \implies m|\left(\frac{3m+1}{2}\right)^2+3 \implies m|13 \implies m=1,13$.For $m=13$ we have $n=20$(not possible) and the other case yeilds $n=2$(not possible).So no solution in this case. Case 2: $3m+1=4n$ In this case we have $m|n^2+3 \implies m|\left(\frac{3m+1}{4}\right)^2+3 \implies m|49 \implies m=1,7,49$ Simple case checking gives us $(m,n)=(49,37),(1,1)$ as the only solution. Case 3:$n^2+3=4m$ In this case we have $n|3m+1 \implies n|3\frac{n^2+3}{4}+1 \implies n|13 \implies n=1,13$ Again simple case check gives us $(m,n)=(43,13)$ as the only solution which is not counted before. The fourth case is $n^2+3=8m$.But note that this is not possible as LHS is $\equiv 4\pmod{8}$ Combining these we get $\boxed{(m,n)=(1,1),(43,13),(49,37)}$ as the only solutions.

thank u jul

From $(1),$ we have $n\not \vdots \;\; 3$ and $3m+1=nk\; (k\in \mathbb{Z}^+$ and $k$ is even) From $(2),$ we have $m \mid \left(\dfrac{3m+1}{k} \right)^2+3\Rightarrow m \mid 3k^2+1\Rightarrow m \mid 9k^2+3,$ note that $m \mid n^2+3$ $\Rightarrow m \mid (3k-n)(3k+n),$ let $d=\gcd (3k-n,3k+n)\Rightarrow d$ is odd, we also have $\left\{ \begin{array}{l} d\mid 6k\Rightarrow d\mid k\\ d\mid 2n\Rightarrow d\mid n \end{array} \right.$ Let $\left\{ \begin{array}{l} k=dx\\ n=dy \end{array} \right. (\gcd(x,y)=1\; \text{and}\; x \; \text{is even,}\; y\; \text{is odd})\Rightarrow m\mid d^2.(3x-y)(3x+y)$ Let $g=\gcd (m,d)\Rightarrow g\mid d \mid n \mid 3m+1\Rightarrow g\mid 1\Rightarrow g=1\Rightarrow m \mid (3x-y)(3x+y)$ Let $s=\gcd (3x-y,3x+y)\Rightarrow s$ is odd, we also have $\left\{ \begin{array}{l} s\mid 6x\Rightarrow s\mid 3x\\ s\mid 2y\Rightarrow s\mid y \end{array} \right. \Rightarrow s\in \{1;3 \}$ If $s=3,$ we have $3\mid y \mid n,$ absurd $\Rightarrow s=1 \Rightarrow \left[ \begin{array}{l} m\mid 3x - y\\ m\mid 3x + y \end{array} \right. \Rightarrow m \le 3x+y\le 3k+n$ $\Rightarrow \dfrac{nk-1}{3}\le 3k+n\Leftrightarrow (k-3)(n-9)\le 28,$ we split the problem into several cases: $\bullet \; k=2\Rightarrow m\mid 13\Rightarrow m\in \{1;13\} \Rightarrow (m,n)=(1,1)$ $\bullet \; k=4 \Rightarrow m\mid 49\Rightarrow m \in \{1;7;49\}\Rightarrow (m,n)\in \{(1,1); (49,37)\}$ $\bullet \; k\ge 6\Rightarrow n-9\le \dfrac{28}{k-3}\le \dfrac{28}{3}\Rightarrow n\le 18\Rightarrow n\in \{1;5;7;11;13;17 \}\Rightarrow (m,n)\in \{(1,1); (43,13)\}$ Hence all possible values of $(m,n)$ are $\boxed{(1,1);(43,13);(49,37)}$

To be fair, the most natural to me method for solving this problem for odd $m,n$ is pretty much the same for all $m,n$ (the only difference is that there are $7+8 = 15$ small cases to check, instead of only $4+4 = 8$, namely $4$ for even $k = \frac{3m+1}{n}$ and $4$ for odd $n$). Here is a solution to the problem for all $m$, $n$.