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

In summary, it was initially thought that the Chinese Remainder Theorem or a combinatorial method could be used to find the smallest positive integer N that satisfies the equations N mod m = 1 for m in {2,3,4,5,6} and N mod 7 = 0. However, it was later discovered that the solution could be found by using the inverse of 3 mod 7 and the Euclidean algorithm to solve a linear Diophantine equation. The solution for N is 301.
  • #1
nomadreid
Gold Member
1,711
223
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.)
 
Physics news on Phys.org
  • #2
nomadreid said:
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.
 
  • Like
Likes Delta2, HallsofIvy and nomadreid
  • #3
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.
 
  • Like
Likes ehild
  • #4
nomadreid said:
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##.
 
  • Like
Likes nomadreid
  • #5
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.:rolleyes:)
 
  • #6
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.
 
  • #7
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.
 
  • #8
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.
 
  • Like
Likes nomadreid
  • #9
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.
 

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

1. What does the equation "N mod m = 1" mean?

The equation "N mod m = 1" means that when N is divided by m, the remainder is equal to 1. Modulus, or mod, is a mathematical operation that calculates the remainder after division.

2. Why is the equation "N mod m = 1" relevant to finding N for the given conditions?

Since N mod 7 = 0 is also given, the equation "N mod m = 1" narrows down the possible values of N. It means that N is one more than a multiple of m, and since N mod 7 = 0, N must also be a multiple of 7. This information reduces the number of possible solutions and makes it easier to find the correct value of N.

3. How do you use the given information to find N?

To find N, we can use the Chinese Remainder Theorem, which states that if we have a system of linear congruences (equations in the form of "N mod m = a"), we can find a unique solution for N as long as the moduli (m values) are pairwise coprime (have no common factors). In this case, the moduli are 2, 3, 4, 5, and 6, which are all pairwise coprime. By solving the system of linear congruences, we get N = 301.

4. Can you explain how the Chinese Remainder Theorem is used to solve this problem?

The Chinese Remainder Theorem involves finding the least common multiple (LCM) of the given moduli (m values). In this case, the LCM of 2, 3, 4, 5, and 6 is 60. We then divide the LCM by each modulus to get a set of numbers (a values) that will be used in the linear congruences. For example, for the modulus 4, the a value is 15, since 60/4 = 15. We then solve the system of linear congruences to get the solution for N.

5. Are there any other methods to solve this problem?

Yes, there are other methods that can be used to solve this problem, such as the Euclidean algorithm or trial and error. However, the Chinese Remainder Theorem is the most efficient and systematic method, especially when dealing with a larger number of moduli.

Similar threads

Back
Top