How to Find the Smallest Integer with Specific Remainders?

  • Context: Undergrad 
  • Thread starter Thread starter CalculusSandwich
  • Start date Start date
  • Tags Tags
    Classes
Click For Summary
SUMMARY

The smallest positive integer that gives a remainder of 4 when divided by 12, 17, 45, or 70 is 4. The discussion highlights the use of equivalence classes, specifically x ≡ 4 (mod 12), x ≡ 4 (mod 17), x ≡ 4 (mod 45), and x ≡ 4 (mod 70). While the approach of multiplying the moduli and adding 4 is mentioned, it does not yield the smallest integer. The least common multiple (LCM) of the moduli can be added to 4 to find subsequent solutions.

PREREQUISITES
  • Understanding of modular arithmetic
  • Familiarity with least common multiples (LCM)
  • Basic knowledge of equivalence classes
  • Ability to solve congruences
NEXT STEPS
  • Study the properties of modular arithmetic in depth
  • Learn how to calculate the least common multiple (LCM) of multiple numbers
  • Explore advanced techniques for solving systems of congruences
  • Investigate the Chinese Remainder Theorem for more complex scenarios
USEFUL FOR

Mathematicians, computer scientists, and students studying number theory or modular arithmetic who are looking to solve congruences and understand integer properties.

CalculusSandwich
Messages
16
Reaction score
0
Find the smallest positive integer which when divided by 12, by 17, by 45 or by 70 gives
a remainder of 4 in each case.

I know I can approach this problem by writing the equivalence classes.

x=4mod12
x=4mod17
x=4mod45 or x=4mod70

I also know I can find x by multiplying 12*17*45 + 4, but this isn't the smallest positive integer.

Can someone help me with a formula I can use?
 
Physics news on Phys.org
Erm... how about the solution x=4?
It is a solution and I don't think there are any smaller positive integers that are also a solution.
 
If you for some reason do not like the number 4, you have to add the lcm of your moduli to get the next.
 

Similar threads

MHB What is the remainder when m+n is divided by 1000 in a trigonometric challenge?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Solving an equation that contains the floor function
  • · Replies 9 ·
Replies
9
Views
4K
Undergrad Solve Coin Sum Problem: Find Combinations for 200p
  • · Replies 13 ·
Replies
13
Views
2K
Undergrad Finding the Largest (or smallest) Value of a Function - given some constant symmetric errors
  • · Replies 3 ·
Replies
3
Views
2K
Prove relation between the group of integers and a subgroup
  • · Replies 6 ·
Replies
6
Views
1K
Undergrad Finding the Smallest n for F(n)=24: A Challenge in Integer Solutions
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Questions on Remainder & Integer Divisibility
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Applying change of basis to vector b_1 doesn't give b'_1?
  • · Replies 8 ·
Replies
8
Views
3K
Undergrad Trying to get the point of some Group Theory Lemmas
  • · Replies 3 ·
Replies
3
Views
2K
Graduate How do I find the change of basis matrix for the JCF of M?
  • · Replies 6 ·
Replies
6
Views
2K