- #1

- 16

- 0

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter chickenguy
- Start date

- #1

- 16

- 0

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

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.

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:

- #3

- 16

- 0

- #4

- 759

- 0

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

- #5

Zurtex

Science Advisor

Homework Helper

- 1,120

- 1

- #6

VietDao29

Homework Helper

- 1,424

- 3

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

Viet Dao,

- #7

lurflurf

Homework Helper

- 2,440

- 138

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

Viet Dao,

- #8

VietDao29

Homework Helper

- 1,424

- 3

Whoops,... N divides d, the remainder is 7. So d > 7.lurflurf said:1,2,4,8,16|16

There are 2 only.

But, in fact... 1 is obvious not the answer...

Viet Dao,

- #9

lurflurf

Homework Helper

- 2,440

- 138

a|b means b/a has no remainderchickenguy said:

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

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

lurflurf

Homework Helper

- 2,440

- 138

good point 5 numbers come out of theVietDao29 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,

d|16 step, but some are extraneous (ie do not meet the original requirements)

- #11

Zurtex

Science Advisor

Homework Helper

- 1,120

- 1

- #12

- 759

- 0

Zurtex said:

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 )

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

Share:

- Replies
- 3

- Views
- 3K