How many of the 1000 smallest positive integers are congruent to 1 modulo 9?

Question

zzr0ck3r · Answer

1,10,19,28, 37, 46, 55.....

zzr0ck3r · Answer

I guess this does not help solve how many...

ganeshie8 · Answer

$$1\le 9k+1\le 1000$$
where $k$ is a nonnegative integer

zzr0ck3r · Answer

that should do it lol

usukidoll · Answer

you need a positive integer that can produce a remainder 1 in modulo 9.. err? try chinese remainder theorem???

anonymous · Answer

wth is that

usukidoll · Answer

ah no wait... it's one of those guessing type things.. try 10 is congruent to 1 mod 9

usukidoll · Answer

are you in number theory?

anonymous · Answer

yeah

usukidoll · Answer

ooh I just passed that course.. :)

ganeshie8 · Answer

hey if you see zzr's first reply, you just need to find the number of terms in that arithmetic progression

usukidoll · Answer

if we're in mod 9 we can't use 1 through 8... and 9 is 0 in mod 9

anonymous · Answer

so are u saying that i should do 1+9(n-1)<1000 and guess for n

usukidoll · Answer

I had a similar problem on my final exam only it was what is least positive integer for 5x = 97 mod 84. grrrr!

usukidoll · Answer

though it looks like your question needs more than 1 answer... so 10 is only part of it x_X

zzr0ck3r · Answer

Do you not understand @ganeshie8 solution? he solved it without anything fancy...

usukidoll · Answer

ahhh do we let k = 1,2,3,4.......

anonymous · Answer

from 1 to 9 there is 1 number
so in 999 there is 111 numbers :D

anonymous · Answer

no 112

anonymous · Answer

if u use th equation 1+9(n-1) we see that 112 would be it not 111

zzr0ck3r · Answer

well $1\le 9k+1\le 1000\iff 0\le k\le 100$

100-0= 100

anonymous · Answer

1000 mod 9=1 so add it to 111

anonymous · Answer

yeah so 112

anonymous · Answer

:)

anonymous · Answer

yeah its 112

anonymous · Answer

does anyone need this problem or can i close it now?

usukidoll · Answer

you can close it :)

ganeshie8 · Answer

@UsukiDoll  do you solve ur question by using eiclid gcd algorithm ?

ganeshie8 · Answer

*euclid

ganeshie8 · Answer

5x = 97 mod 84

guess there are several ways to solve this, i think euclid gcd algorithm is the straightforward one..

usukidoll · Answer

yeah I did... I got... -17 and 1 when I did the backwards Euclidean Algorithim 
I did remember using gcd.

anonymous · Answer

also fyi ganeshi8 ur way was correct, using that inequality statement

usukidoll · Answer

I did forwards and backwards EA

usukidoll · Answer

I guess I might have passed the final to get a B in the number theory course ^_^

ganeshie8 · Answer

nice :) i was just thinking about how chinese remaidner thm applies here.. thats all

anonymous · Answer

what is the chinese remainder theorm?

ganeshie8 · Answer

nvm i see it !

usukidoll · Answer

since 9 = 3 x 3 I figured  x congruent to 1 mod 3 twice but that would take forever.

anonymous · Answer

chine's dont work here :O
its an other problem

ganeshie8 · Answer

Makes sense !
5x = 97 mod 84

we can solve below simpler system using chinese remainder thm
5x = 97 mod 3
5x = 97 mod 4
5x = 97 mod 7

usukidoll · Answer

well I'm done with school for now so my brain is in mmorpg land

usukidoll · Answer

UGH! WHAT THE Fffff :(. now I feel like ssssssssssss........thanks really. :'(

usukidoll · Answer

because I know what Chinese Remainder theorem is... but since I wasn't given a system of congruences, it would've been an incongruent solution type thing.... :'(

ganeshie8 · Answer

:) chinese remainder thm works as the numbers are coprime  (3, 4, 7)


84 = 3*4*7

usukidoll · Answer

-______________________-!

anonymous · Answer

wth is the chinese remainder theorm ;(

usukidoll · Answer

it's a super long computation that requires 2 or more congruence systems.

ganeshie8 · Answer

hey chinese remainder thm is a method to solve system of congriences

usukidoll · Answer

you know that pos problem was the first question on my final >:O/// sooo gawd the fact that I could've used CRT.. damn it

anonymous · Answer

how old are u guys?

usukidoll · Answer

26

ganeshie8 · Answer

chinese remainder thm allows you to solve a system of linear congriences :  $$a_1x\equiv b_1\pmod{c_1} $$
$$a_2x\equiv b_2\pmod{c_2} $$
$$a_3x\equiv b_3\pmod{c_3} $$
$$\cdots  $$

anonymous · Answer

oh, I'm 12

ganeshie8 · Answer

$$12\equiv 26\pmod{14}$$

usukidoll · Answer

O_X! what's a 12 year old doing learning number theory

anonymous · Answer

#Asian

ganeshie8 · Answer

they have a weird course by name "applied math" where they teach modular arithmetic, number systems, statistics, probability and evverything else in math in just 6 months

anonymous · Answer

@UsukiDoll what college did u go to.

anonymous · Answer

@ganeshie8 but some cities allow children to skip grades or go to diff places for a period (as in class) to learn higher math.

ganeshie8 · Answer

ikr :) I think you will understand chinese remainder thm easily and it is a very interesting thm

look it up in google when free

anonymous · Answer

anyway ganeshie do u live in the northern or southern part of india. Just curious

ganeshie8 · Answer

see if you can try these hard problems on your own first

(they are not hard once you know chinese remainder thm, then you can do them in less than 10 seconds! )

ganeshie8 · Answer

i live in bangalore and it is south india.. you live in india too ?

anonymous · Answer

119 and no I live in America but I am planning to go to India this year to help out in the slums.

usukidoll · Answer

OMG THAT pirate problem! That was in my book

anonymous · Answer

wth a pirate's problem?

usukidoll · Answer

omfg read what ganeshie's attachment is displaying

usukidoll · Answer

p.s. for the first problem I ate the eggs.

anonymous · Answer

lawl and second problem is 301

ganeshie8 · Answer

119 is answer for #8 ?

its a classic problem lol i think all those probloems can be worked without chines remainder theorem.. but takes lot of time and donkey work!

ganeshie8 · Answer

let me check the answer key, one sec..

usukidoll · Answer

school is over.. christmas break for me......... so my solving ain't here XD

anonymous · Answer

for the third one the pirate's problem what should i do after this

usukidoll · Answer

you beat up the pirates and say give me coins

anonymous · Answer

x%17=R3
x%16=R10
x%15=R0

ganeshie8 · Answer

looks you nailed them !!! http://gyazo.com/b6f2ee82da6b39953bf3f95f2cd475af

usukidoll · Answer

wtf... hey Who is heck is DHL global and what is it doing with my Mathematical Biology supplemental book?

anonymous · Answer

wait can u explain the third one

anonymous · Answer

i know n(the number)=15x

ganeshie8 · Answer

@UsukiDoll  you want to try explaining him as your memory is fresh
il need to review..

anonymous · Answer

and all that other congruence statement

anonymous · Answer

but what to do after that

usukidoll · Answer

awww sweettttt my other has 3 day priority mail... I'm sorry what? that problem was from last year... wasurimapelleta gomennasai ^_^

anonymous · Answer

wait i got it anyway

anonymous · Answer

so u make all the congruence statements substituted inside, which causes u with 1 final equation and thats how u do it

ganeshie8 · Answer

yes this is a great start
x%17=R3
x%16=R10
x%15=R0

anonymous · Answer

-150 +4080s.

ganeshie8 · Answer

we get this system :

x = 17a + 3
x = 16b + 10
x = 15c

anonymous · Answer

and thats the final equation however u subsitute s for 1 since thats the smallest number of coins and so forth

anonymous · Answer

anyway so how's India

ganeshie8 · Answer

idk how you got -150 +4080s.
im getting something else.. wil catchup after lunch... :)

ganeshie8 · Answer

you should get 3930 for pirates problem..

dan815 · Answer

hey

dan815 · Answer

what does 1 modulo 9 mean

dan815 · Answer

is it remainedder 1 when u divide by 9

usukidoll · Answer

mod 9 is = 0,1,2,3,4,5,6,7,8

1 is the remainder yes... 

so we can't use 1-8 because those numbers are too small for mod 9... 

the #9 is 0 in mod 9 and the #10 is 1 in mod 9.

dan815 · Answer

ohh okay!!