N mod m =1 for 1<m<7, N mod 7=0. Find N. (N=301, but how?)

[nomadreid]

Homework Statement

N is the smallest positive integer such that N mod m = 1 for m in {2,3,4,5,6} and N mod 7 = 0. Find N.

Relevant Equations

This is supposed to be done without number theory theorems, and without a computer program, and of course not trial-and-error.

First, I know the answer: 301. I thought (despite the injunction that the problem is to be done without number theory) that the Chinese Remainder Theorem might be of help (if I would use a subset which contained only relatively primes), but that didn't get very far. I also tried to spot a pattern in a trial-and-error program (again, despite the injunction), but failed there. I thought it might be a combinatorial method, but that also did not yield any results. The solution is supposed to be relatively simple, so I am missing something obvious. (A bit embarrassing, as it is a problem for a 12-year old private student.)

 

[Mark44]

Problem Statement: N is the smallest positive integer such that N mod m = 1 for m in {2,3,4,5,6} and N mod 7 = 0. Find N.
Relevant Equations: This is supposed to be done without number theory theorems, and without a computer program, and of course not trial-and-error.

First, I know the answer: 301. I thought (despite the injunction that the problem is to be done without number theory) that the Chinese Remainder Theorem might be of help (if I would use a subset which contained only relatively primes), but that didn't get very far. I also tried to spot a pattern in a trial-and-error program (again, despite the injunction), but failed there. I thought it might be a combinatorial method, but that also did not yield any results. The solution is supposed to be relatively simple, so I am missing something obvious. (A bit embarrassing, as it is a problem for a 12-year old private student.)

From the various N mod m equations, it must be true that N - 1 is divisible, respectively, by 2, 3, 4, 5, and 6. In addition, N must be divisible by 7.

Since N - 1 is divisible by both 2 and 3, it's automatically divisible by 6. Also, since N - 1 is divisible by 4, it must have two factors of 2. So N - 1 must be some multiple of 3 * 4 * 5 = 60; i.e., N - 1 = 60k for some pos. integer k.

Further 7 | N, so all that's left is to look for the smallest value of (60k + 1) that is divisible by 7.

 

[nomadreid]

Thank you for your answer, Mark44. However, whereas you have reduced the amount of trial-and-error, you have not eliminated it. However, from there, it is possible to proceed as follows:
60k+1 = 63k-3k+1; since 7|63k, then 7|(-3k+1). Setting -3k+1 =7 as the easiest case, k=-2.
Since 7|(-3k+1) , then 7|[(-3k+1)-21] , so 7|[(-3(k+7)+1] .
Putting the last two lines together, 7|[(-3)(-2+7)+1]i.e, -3(5)+1, so the k=5, so N=60(5)+1 = 301.
However, I was hoping for something more direct.

 

[PeroK]

Thank you for your answer, Mark44. However, whereas you have reduced the amount of trial-and-error, you have not eliminated it. However, from there, it is possible to proceed as follows:
60k+1 = 63k-3k+1; since 7|63k, then 7|(-3k+1). Setting -3k+1 =7 as the easiest case, k=-2.
Since 7|(-3k+1) , then 7|[(-3k+1)-21] , so 7|[(-3(k+7)+1] .
Putting the last two lines together, 7|[(-3)(-2+7)+1]i.e, -3(5)+1, so the k=5, so N=60(5)+1 = 301.
However, I was hoping for something more direct.

If you start where Mark left off you get an equation:

$4k +1 = 0 \ mod \ 7$

Or

$3k = 1 \ mod \ 7$

Maybe that's still trial and error, but it's fairly trivial. You are effectively finding the inverse of $3$ in modulo $7$.

 

[nomadreid]

Thanks, PeroK. Yes, that is shorter and simpler than mine.
So, thank you Mark44 and PeroK together. (Mark44's part will be easy enough to explain to a 12-year old; how easily he will understand my explanation about inverses modulo 7 will be interesting.)

 

[HallsofIvy]

3*1= 3, 3*2= 6, 3*3= 9= 7+ 2= 2 (mod 7), 3*4= 12= 7+ 5= 5 (mod 7), 3*5= 15= 14+ 1= 1 (mod 7), 3*6= 18= 14+ 4= 4 (mod 7). So the multiplicative inverse of 3 (mod 7) is 5.

More generally, b is the inverse of a, mod n, if and only if ab= 1 (mod n) which is equivalent to ab= kn+ 1 for some integer k. That is equivalent to the Diophantine equation ab- kn= 1.

 

[nomadreid]

Thanks, HallsofIvy. (Delayed answer because of travels.) I presume this is taking off from the comment that I am looking for the inverse x of 3 mod 7, translating this into the Diophantine equation 3x-7k =1. I believe one can say that this has a solution because 3 and 7 are relatively prime, but I am not sure whether there is a way to solve this equation outside of using trial and error, since it is a single equation in two unknowns.

 

[HallsofIvy]

Since 7 is a relatively small number, one way to find the multiplicative inverse of 3, mod 7, is by doing the multiplications:
3*2= 6, 3*3= 9= 2, 3*4= 12= 5, 3*5= 15= 1 (mod 7). The multiplicative inverse of 3, mod 7, is 5.

A more "sophisticated" method (and better for large numbers) is to say that 3x= 1 (mod 7) is the same as 3x= 1+ 7n for some integer n and that is the same as 3x- 7n= 1. That is a linear "Diophantine equation" since both x and n must be integers. It can by solved using the "Euclidean algorithm". 3 divides into 7 twice with remainder 1: 7- 3(2)= 1. That can be written as 3(-2)- 7(-1)= 1. So, immediately, x= -2, n= -1 is a solution. But then it is easy to see that x= -2+ 7k, n= -1+ 3k is also a solution for any integer, k: 3(-2+ 7k)- 7(-1+ 3k)= -6+ 7+ 21k- 21k. Since we are dealing with "modulo 7" we want our answer between 0 and 7: take k= 1 so x= -2+ 7= 5.

 

[nomadreid]

Thanks, HallsofIvy. (It seems that you posted the same answer twice, unless there is some difference I am overlooking.) Most of this procedure looks very similar to the procedure I elaborated in post #3, albeit yours is better expressed.