Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Urgent Question

  1. Aug 20, 2005 #1
    Hi everyone, there is this question that is really bugging me and i am wondering if you guys could help me out.


    When a certain positive integer N is divided by a positive integer d, tje remainder is 7. if 2N+3 is divided by d, the remainder is 1. Find all possible values of d.


    Pleasse help me with this one, as it is urgent :surprised
     
  2. jcsd
  3. Aug 20, 2005 #2

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    N = 7 (mod d)

    2N + 3 = 1 (mod d)

    Substituting:

    2*7 + 3 = 1 (mod d)

    17 = 1 (mod d)

    I wouldn't say it's too hard to work it out from there. If a simple way doesn't occur to you then just check all the values for d less than 17.
     
    Last edited: Aug 20, 2005
  4. Aug 20, 2005 #3
    sorry, but i happen to be very bad at maths, so could you please give me the whole explanation and asnwers??? i don't understand your explanation
     
  5. Aug 21, 2005 #4
    Hmm...I have not studied modulus, and my method & solution are likely incorrect :frown:

    Let there be two numbers, p & q, defined as follows:
    [tex] \frac{{n - 7}}{d} = p [/tex]
    and
    [tex] \frac{{2n + 3 - 1}}{d} = 2\left( {\frac{{n + 1}}{d}} \right) = q [/tex]

    Now, from the conditions of the problem, it is clear that [tex] \left( {p,q} \right) \in \mathbb{Z}^2 [/tex] and [itex] d > 7 [/itex]. Next, we just solve this system of equations for [itex] d [/itex]. From the first equation, we find that [itex] n = pd + 7 [/itex]. Substituting this to solve for [itex]d[/itex] in the second equation:
    [tex] 2\left( {\frac{{pd + 8}}{d}} \right) = q \Rightarrow \frac{8}{d} = \frac{q}{2} - p \Rightarrow d = \frac{{16}}{{q - 2p}} [/tex]

    Because [tex] \left( {p,q,d} \right) \in \mathbb{Z}^3 [/tex] and [tex] d > 7 [/tex],

    ...therefore [tex] d = \left\{ {8,16} \right\} [/tex].

    And those are the only two solutions for [itex] d [/itex].
    (I may be wrong...:frown:)
     
  6. Aug 21, 2005 #5

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    bomba923 the idea is that we don't give answers, we just try and help the person. Though you are on the right track there is no reason for d to be greater than 7, there are in fact a total of 5 solutions for d.
     
  7. Aug 21, 2005 #6

    VietDao29

    User Avatar
    Homework Helper

    Why 5? :confused: I think there are only 4.
    Viet Dao,
     
  8. Aug 21, 2005 #7

    lurflurf

    User Avatar
    Homework Helper

    1,2,4,8,16|16
     
  9. Aug 21, 2005 #8

    VietDao29

    User Avatar
    Homework Helper

    Whoops,... N divides d, the remainder is 7. So d > 7.
    There are 2 only. :wink:
    But, in fact... 1 is obvious not the answer...
    Viet Dao,
     
  10. Aug 21, 2005 #9

    lurflurf

    User Avatar
    Homework Helper

    a|b means b/a has no remainder
    or that there exist and integer s such that
    as=b
    in the mod notation
    a=b (mod c)
    means c|(a-b)
    the conditions given can be written
    d|(N-7)
    d|(2N+2)
    a basic theorem of arithmetic say
    if d|x and d|y
    then
    d|(ax+by) for all integers a and b
    so
    d|(a(N-7)+b(2N+2))
    so since we do not know N chose a and b relatively prime so that
    a(N-7)+b(2N+2) is a positive integer
    this is quite easily done
    as we want a+2b=0
    and 2b-7a>0
    and gcd(a,b)=1
    once it is
    d|(a(N-7)+b(2N+2))
    will be written
    d|r
    where r is a known natural number
    the factors of r are possibilities for d
     
  11. Aug 21, 2005 #10

    lurflurf

    User Avatar
    Homework Helper

    good point 5 numbers come out of the
    d|16 step, but some are extraneous (ie do not meet the original requirements)
     
  12. Aug 21, 2005 #11

    Zurtex

    User Avatar
    Science Advisor
    Homework Helper

    Yes, I'm sorry for confusing the situation there, the definition of remainder that I had in my head was perhaps a little too liberal for the question that was given.
     
  13. Aug 21, 2005 #12
    Well, [tex] d > 7 [/tex] because divisors less than or equal to seven cannot produce quotients with remainders of seven (it wouldn't make any sense, though perhaps I should have mentioned this in my solution post :frown:)
    *If we remove the condition d > 7, then there are indeed five solutions: d={1,2,4,8,16}. But d={1,2,4} will not produce remainders of seven...so eliminating those, you are left with d={8,16} as the only possible solutions (with the "remainder seven" requirement...and d=1 divides all integers anyway :shy:)
     
    Last edited: Aug 21, 2005
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Urgent Question
  1. HELP : URGENt (Replies: 3)

Loading...