Urgent Question

1. Aug 20, 2005

chickenguy

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. Aug 20, 2005

Zurtex

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
3. Aug 20, 2005

chickenguy

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

4. Aug 21, 2005

bomba923

Hmm...I have not studied modulus, and my method & solution are likely incorrect

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

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

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

...therefore $$d = \left\{ {8,16} \right\}$$.

And those are the only two solutions for $d$.
(I may be wrong...)

5. Aug 21, 2005

Zurtex

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.

6. Aug 21, 2005

VietDao29

Why 5? I think there are only 4.
Viet Dao,

7. Aug 21, 2005

lurflurf

1,2,4,8,16|16

8. Aug 21, 2005

VietDao29

Whoops,... N divides d, the remainder is 7. So d > 7.
There are 2 only.
But, in fact... 1 is obvious not the answer...
Viet Dao,

9. Aug 21, 2005

lurflurf

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

10. Aug 21, 2005

lurflurf

good point 5 numbers come out of the
d|16 step, but some are extraneous (ie do not meet the original requirements)

11. Aug 21, 2005

Zurtex

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.

12. Aug 21, 2005

bomba923

Well, $$d > 7$$ 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 )
*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?