Results 1 to 2 of 2

Thread: Common Divisor

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    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}$

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: Oct 25th 2010, 05:45 AM
  2. great common divisor
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Mar 3rd 2010, 08:40 AM
  3. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Nov 23rd 2009, 12:36 AM
  4. common divisor proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 6th 2009, 11:05 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 25th 2008, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum