1. ## Common Divisor

An integer $\displaystyle n>1$ has the properties that $\displaystyle n|(35m+26)$ and $\displaystyle n|(7m+3)$ for some integer $\displaystyle m$, what is $\displaystyle n$?

My solution is as follows:

Let $\displaystyle n>1$ and $\displaystyle n|(35m+26)$ and $\displaystyle n|(7m+3)$, where $\displaystyle n \in \mathbb{N}$ and $\displaystyle m \in \mathbb{Z}$. Then

$\displaystyle (35m+26) \equiv (7m+3) \equiv 0 \text{(mod n)}$.

Let $\displaystyle Z_n$ be a set of relation $\displaystyle mR0$ defined by $\displaystyle (35m+26) \equiv (7m+3) \equiv 0 \text{(mod n)}$. We find the integer $\displaystyle m$, and the result is

$\displaystyle Z_n = Z_{11}=[9]$

Remark: The solution involved repeating input of integer $\displaystyle m$ until $\displaystyle (35m+26)$ and $\displaystyle (7m+3)$ have a common divisor greater than 2, which doesn't seem very mathematical.

Question:
1. Could anyone show me a better solution?
2. Is it possible to solve this using the Euclidean Algorithm?

2. Hello, novice!

$\displaystyle \text{An integer }n>1 \text{ has the property that: }\:n|(35m+26)\,\text{ and }\,n|(7m+3),$ .$\displaystyle \text{ for some integer }m.$

.$\displaystyle \text{What is }n\:?$

We are given: .$\displaystyle \begin{array}{cccccc}[1] & \dfrac{35m+26}{n} &=& a & \text{ for some integer } a \\ \\[-3mm] [2] & \dfrac{7m+3}{n} &=& b & \text{for some integer }b \end{array}$

$\displaystyle \begin{array}{cccccc} \text{From [1], we have:} & m &=& \dfrac{an-26}{35} & [3]\\ \\[-3mm] \text{From [2], we have:} & m &=& \dfrac{bn-3}{7} & [4]\end{array}$

Equate [3] and [4]: .$\displaystyle \frac{an-26}{35} \:=\:\frac{bn-3}{7}$

. . . Multiply by 35: .$\displaystyle an - 26 \;=\;5bn - 15 \quad\Rightarrow\quad an - 5bn \:=\:11$

. . . . . . . . .Factor: .$\displaystyle n(a - 5b) \:=\:11 \quad\Rightarrow\quad n \:=\:\frac{11}{a-5b}$

Hence, the only integer values of $\displaystyle n$ are: .$\displaystyle 1 \text{ and }11.$

. . Therefore: .$\displaystyle {\color{blue}n \:=\:11}$