Find all possible values of d

  • Thread starter chickenguy
  • Start date
16
0

Main Question or Discussion Point

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
 

Answers and Replies

Zurtex
Science Advisor
Homework Helper
1,120
1
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:
16
0
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
 
732
0
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:)
 
Zurtex
Science Advisor
Homework Helper
1,120
1
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
Homework Helper
1,417
1
Zurtex said:
there are in fact a total of 5 solutions for d.
Why 5? :confused: I think there are only 4.
Viet Dao,
 
lurflurf
Homework Helper
2,419
122
VietDao29 said:
Why 5? :confused: I think there are only 4.
Viet Dao,
1,2,4,8,16|16
 
VietDao29
Homework Helper
1,417
1
lurflurf said:
1,2,4,8,16|16
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,
 
lurflurf
Homework Helper
2,419
122
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 :surprised
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
Homework Helper
2,419
122
VietDao29 said:
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,
good point 5 numbers come out of the
d|16 step, but some are extraneous (ie do not meet the original requirements)
 
Zurtex
Science Advisor
Homework Helper
1,120
1
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.
 
732
0
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, [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:

Related Threads for: Find all possible values of d

Replies
7
Views
1K
Replies
4
Views
564
Replies
8
Views
3K
Replies
7
Views
4K
Replies
14
Views
3K
Replies
1
Views
1K
Replies
2
Views
1K
Top