# 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