- #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

- 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,423

- 2

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,432

- 132

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

Viet Dao,

- #8

VietDao29

Homework Helper

- 1,423

- 2

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,432

- 132

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,432

- 132

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

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

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

- Replies
- 3

- Views
- 3K

- Replies
- 14

- Views
- 3K

- Replies
- 1

- Views
- 1K

- Replies
- 2

- Views
- 1K

- Replies
- 1

- Views
- 2K

- Replies
- 7

- Views
- 2K

- Replies
- 4

- Views
- 5K

- Last Post

- Replies
- 5

- Views
- 2K

- Replies
- 4

- Views
- 619

- Replies
- 1

- Views
- 1K