"Finding Smallest n for Congruence Modulo Homework

  • Thread starter Thread starter shizukusan
  • Start date Start date
Click For Summary

Homework Help Overview

The problem involves finding the smallest positive integer n that satisfies a series of congruences, specifically n = 1 (mod 2), n = 2 (mod 3), n = 3 (mod 4), n = 4 (mod 5), n = 5 (mod 6), n = 6 (mod 7), n = 7 (mod 8), n = 8 (mod 9), and n = 9 (mod 10). The context is within number theory, particularly focusing on modular arithmetic.

Discussion Character

  • Exploratory, Assumption checking, Problem interpretation

Approaches and Questions Raised

  • Participants discuss the implications of the first congruence, noting that n must be odd. There is an exploration of testing odd numbers against the other congruences. Some participants express concerns about the feasibility of finding a solution through trial and error, especially regarding the need for a proof.

Discussion Status

The discussion is ongoing, with participants sharing their attempts and considerations. Some guidance has been offered regarding starting points and the nature of the numbers that satisfy the congruences. There is an acknowledgment of the challenge in providing a proof alongside finding the solution.

Contextual Notes

Participants mention the need to provide a proof for their findings, which adds a layer of complexity to the problem-solving process. There is also a reference to the potential size of the numbers involved, with one participant noting that reaching the 400s is not particularly large in this context.

shizukusan
Messages
2
Reaction score
0

Homework Statement



Find, with proof, the smallest positive integer n that satisfy all the congruences.

n = 1 (mod 2)
n = 2 (mod 3)
n = 3 (mod 4)
n = 4 (mod 5)
n = 5 (mod 6)
n = 6 (mod 7)
n = 7 (mod 8)
n = 8 (mod 9)
n = 9 (mod 10)

Homework Equations



Let a,b,m within Z with m > 0. Then, a = b mod m is m|a-b.
(not sure if relevant or not)

The Attempt at a Solution



I tried to figure out what some of the ristriction on n
(ie - has to be odd since n = 1 (mod 2))
but didn't get too far.
 
Physics news on Phys.org
The first congruence tells you that n must be odd. If you try odd numbers, starting from 3, on the other congruences, what do you get?
 
I sort of tried that approach using the other ristrictions but started to get into the 400s. (with only considering 3 of the 9 ristrictions).

plus, I need to provide a proof and this way is probably not going to work as a proof.
 
400 is hardly a large number :smile:.

Look, if you want strictly positive integers, the smallest that satisfy the first congruence is 3. Now, the smallest that satisfies the first two is 5. Now, what is the smallest that satisfies the first three?

When you get to the last one, you will have the smallest that satisfies all; the steps are a valid proof.
 

Similar threads

  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 27 ·
Replies
27
Views
3K
  • · Replies 3 ·
Replies
3
Views
3K
  • · Replies 11 ·
Replies
11
Views
2K
  • · Replies 1 ·
Replies
1
Views
6K
Replies
4
Views
2K
Replies
2
Views
2K
  • · Replies 9 ·
Replies
9
Views
3K
Replies
4
Views
2K
Replies
15
Views
4K