# Common Divisor

• Jun 6th 2010, 09:13 AM
novice
Common Divisor
An integer $n>1$ has the properties that $n|(35m+26)$ and $n|(7m+3)$ for some integer $m$, what is $n$?

My solution is as follows:

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

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

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

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

Remark: The solution involved repeating input of integer $m$ until $(35m+26)$ and $(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?
• Jun 6th 2010, 11:05 AM
Soroban
Hello, novice!

Quote:

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

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

We are given: . $\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}$

$\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]: . $\frac{an-26}{35} \:=\:\frac{bn-3}{7}$

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

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

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

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