Common Divisor

**novice** · June 6th 2010, 09:13 AM

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?

**Soroban** · June 6th 2010, 11:05 AM

Hello, novice!

$\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]<br /> [2] & \dfrac{7m+3}{n} &=& b & \text{for some integer }b \end{array}$

$\begin{array}{cccccc}<br /> \text{From [1], we have:} & m &=& \dfrac{an-26}{35} & [3]\\ \\[-3mm]<br /> \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}$

Thread: Common Divisor

LinkBack

Thread Tools

Display

Common Divisor

Similar Math Help Forum Discussions

[SOLVED] Least common multiple - Greatest common divisor

great common divisor

Greatest Common Divisor.

common divisor proof

greatest common divisor

Search Tags