3, 5, 7 & 11으로 나눌 때 각각 2, 4, 6 & 1의 나머지를 남기는 가장 작은 정수는 무엇입니까?

대답:

아래를 참조하십시오.

설명:

이 문제는 소위 Chinese Remainder Theorem (CRM)의 응용으로 해결됩니다.

주어진

# {(x equiv r_1 mod m_n), (x equiv r_2 mod m_2), (cdots ""cdots ""cdots),

전화 걸기 #m = m_1m_2 cdots m_n # 와

#M_k = m / m_k EE t_k | t_k M_k equiv 1 mod m_k #

지금 부름 #s_k = t_k M_k # 우리는

#x = 합계 (k = 1) ^ n s_k r_k #

이 예에서

# r_1 = 2, r_2 = 4, r_3 = 6, r_4 = 1 #

# m_1 = 3, m_2 = 5, m_3 = 7, m_4 = 11 #

그때

# t_1 = 1, t_2 = 1, t_3 = 2, t_4 = 2 # 과

#x = 3884 # 솔루션입니다.

노트

이 방법을 사용하면 솔루션을 찾을 수 있으며 결국에는 가장 작은 솔루션을 찾을 수 있습니다. 이 경우 #419# 가장 작은 솔루션입니다.