Results 1 to 2 of 2

Math Help - Common Divisor

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

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

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,751
    Thanks
    651
    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}

    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: October 25th 2010, 05:45 AM
  2. great common divisor
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 3rd 2010, 08:40 AM
  3. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 12:36 AM
  4. common divisor proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 6th 2009, 11:05 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2008, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum