Number Theory

there is exactly 413 students

21*19+14 = 413

23*17+22 = 413

The American Mathematics College is holding its orientation for incoming freshmen. The incoming freshman class contains fewer than 500 people. When the freshmen are told to line up in columns of 23, 22 people are in the last column. When the freshmen are told to line up in columns of 21, 14 people are in the last column. How many people are in the incoming freshman class?

N=23Y-1        and         N=21Q+14

so

\(23Y-1=21Q+14\\ 23Y-21Q=15\\ \)

First find a solution to 23Y-21Q=1   then I will multiply through by 15 to get one solution that i actually want.

I am going to use the euclidean algorithm for this and then the extended euclidean algorithm.

23= -1(-21) +2

-21= -11(2)+1

so

-21 + 11(2) = 1

-21 + 11 [ 23+1(-21) ] =1

-21 +11(-21) +11*23   = 1

12(-21)        + 11*23   = 1

23(11     )    -21 (12   )=1     

23(11*15     )    -21 (12*15   )= 15

23(165     )    -21 (180   )= 15

So one solution will be  Y=165       and  Q= 180   

But that is not the only solution and maybe it is not the solution we want

Becasue... our N value muct be between 0 and 500

So I want a general solution

23(165     )    -21 (180   )= 15

I can add 23*21K and then take it away again and the answer will still be 15.   I do it like this.

23(165 + 21K     )    -21 (180 +23K  )= 15

So the general solution is

Y=165 + 21K       and      Q=180+23K

N= 23Y-1

N= 23[165+21K]-1

N=23*165  + 23*21K -1

N= 3795   + 483K  -1

N= 3794 + 483K

You can check by using the equation, it will work out the same.

Now

0< N < 500

0 < 3794 + 483K < 500

-3794 < 483K < -3295

-7.8 < K < -6.8

K= -7 is the only solution sind all the pronumerals used including K are integers.

So 

N = 3794 +483*-7 = 413

There must be exactly 413 students.

Let m be the number of columns in the first case  and  n be the  number of columns in the second

So....the total number of students  = the total number of students

23 * m   + 22    =  21 * n + 14         subtract  22 from each side

23m  =   21n - 8       divide both sides by 23

m =  (21n) / 23   -  8/23

We are looking for a value  of  n  such that when  21 n  is divided by 23.....the remainder  = 8

So we have that

(21n) mod (23)   =  8

This will happen when n  = 19  ⇒  m = 17

So.....the total number of  students  =  21 (19) + 14  = 413

Hi Chris,

Thanks for your answer :)

I am just looking at this last bit.

(21n) mod (23)   =  8       Yes I get this.

This next step, did you work that out just by trialing lots of values?

This will happen when n  = 19  ⇒  m = 17

I looked at it this way:

N = 23m + 22        (1)                  m is an integer

N = 21n + 14         (2)                  n is an integer

From (1) and (2) we have:   

21n - 23m = 8

or  21(n-m) -2m = 8 

or 21(n-m)/2  - m = 4    (3)

Now (n-m)/2 must be an integer to satisfy (3).

Try (n - m)/2 = 1    (4)

Put this into (3) to get 21*1 - m = 4  or m = 17    (5)

From (4) and (5)   n = 2 + m = 2 + 17 = 19  (6)

Put (5)  into (1) (or (6) into (2)):  N = 23*17 + 22 = 413.

What if (n - m)/2 = 2 

21*2 - m = 4 so m = 38.  This time n = 4 + m = 42.  Hence N = 23*38 + 22 = 896 which is greater than 500.

Clearly, larger values of (n - m)/2 will produce even larger values of N, so N = 413.