What is the range of possible values for the divisor d in this division problem?

[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

 

[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.

 

[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

 

[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...)

 

[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.

 

[VietDao29]

there are in fact a total of 5 solutions for d.

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

 

[lurflurf]

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

1,2,4,8,16|16

 

[VietDao29]

1,2,4,8,16|16

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,

 

[lurflurf]

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

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

 

[lurflurf]

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,

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

 

[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.

 

[bomba923]

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.

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:)