# Find all possible values of d

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

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

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.

Homework Helper
Zurtex said:
there are in fact a total of 5 solutions for d.
Why 5? I think there are only 4.
Viet Dao,

Homework Helper
VietDao29 said:
Why 5? I think there are only 4.
Viet Dao,
1,2,4,8,16|16

Homework Helper
lurflurf said:
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,

Homework Helper
chickenguy said:
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

Homework Helper
VietDao29 said:
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)

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.

bomba923
Zurtex said:
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:)

Last edited: