Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

tst2

2006 China TST (정수) 문제 1.

n | (a + 1) n - a n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mrow data-mjx-texclass="ORD"><mo stretchy="false">|</mo></mrow><mo stretchy="false">(</mo><mi>a</mi><mo>+</mo><mn>1</mn><msup><mo stretchy="false">)</mo><mi>n</mi></msup><mo>-</mo><msup><mi>a</mi><mi>n</mi></msup></math>

을 만족하는 양의 정수 순서쌍

(a, n) <math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>a</mi><mo>,</mo><mi>n</mi><mo stretchy="false">)</mo></math>

을 모두 찾아라. [2006 China TST] 풀이) 더보기

n > 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mo>&gt;</mo><mn>1</mn></math>

이라고 하자.

p <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>p</mi></math>

n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>

을 나누는 최소 소인수라 하자. 만약

p | a + 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>p</mi><mrow data-mjx-texclass="ORD"><mo stretchy="false">|</mo></mrow><mi>a</mi><mo>+</mo><mn>1</mn></math>

p | a <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>p</mi><mrow data-mjx-texclass="ORD"><mo stretchy="false">|</mo></mrow><mi>a</mi></math>

라면 모두를 나누게 되어 모순이다. 따라서

gcd (p, a) = gcd (p, a + 1) = 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mtext>gcd</mtext><mo stretchy="false">(</mo><mi>p</mi><mo>,</mo><mi>a</mi><mo stretchy="false">)</mo><mo>=</mo><mtext>gcd</mtext><mo stretchy="false">(</mo><mi>p</mi><mo>,</mo><mi>a</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></math>

mod p <math xmlns="http://www.w3.org/1998/Math/MathML"><mtext>mod</mtext><mstyle scriptlevel="0"><mspace width="0.278em"></mspace></mstyle><mi>p</mi></math>

a <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math>

b <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math>

가 존재한다. 따라서 다음 식을 얻는다. $$ (a+1)^n\equiv a^n (\textup{mod} \;p) \to (b+1)^n\equiv (ab+b)^n\equiv (ab)^n\equiv 1(\textup{mod} \;.. 2024. 2. 11.

멋진 정수론 문제들 정말 좋은 문제들이니 충분한 고민을 거쳐 풀어보자. 문제1 : 다음 조건을 만족하는 양의 정수 순서쌍

(a, b, c) <math xmlns="http://www.w3.org/1998/Math/MathML"><mo stretchy="false">(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">)</mo></math>

을 모두 구하여라.

lcm(a,b,c)=ab+bc+ca4<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><mtext>lcm</mtext><mo stretchy="false">(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">)</mo><mo>=</mo><mfrac><mrow><mi>a</mi><mi>b</mi><mo>+</mo><mi>b</mi><mi>c</mi><mo>+</mo><mi>c</mi><mi>a</mi></mrow><mn>4</mn></mfrac></math>

[Japan 2020 Final] (sol) 더보기 일반성을 잃지않고

a \geq b \geq c <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mo>\geq</mo><mi>b</mi><mo>\geq</mo><mi>c</mi></math>

a | lcm (a, b, c) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mrow data-mjx-texclass="ORD"><mo stretchy="false">|</mo></mrow><mtext>lcm</mtext><mo stretchy="false">(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">)</mo></math>

a | a b + c a <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mrow data-mjx-texclass="ORD"><mo stretchy="false">|</mo></mrow><mi>a</mi><mi>b</mi><mo>+</mo><mi>c</mi><mi>a</mi></math>

a | b c <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mrow data-mjx-texclass="ORD"><mo stretchy="false">|</mo></mrow><mi>b</mi><mi>c</mi></math>

이다. 따라서

lcm (a, b, c) \leq b c <math xmlns="http://www.w3.org/1998/Math/MathML"><mtext>lcm</mtext><mo stretchy="false">(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">)</mo><mo>\leq</mo><mi>b</mi><mi>c</mi></math>

가 성립한다.. 즉, 최댓값이

b c <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi><mi>c</mi></math>

gcd (b, c) > 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mtext>gcd</mtext><mo stretchy="false">(</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo stretchy="false">)</mo><mo>&gt;</mo><mn>1</mn></math>

b c / p <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi><mi>c</mi><mrow data-mjx-texclass="ORD"><mo>/</mo></mrow><mi>p</mi></math>

꼴이 된다. 그런데,

a b + b c + c a \geq 3 b c <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>b</mi><mo>+</mo><mi>b</mi><mi>c</mi><mo>+</mo><mi>c</mi><mi>a</mi><mo>\geq</mo><mn>3</mn><mi>b</mi><mi>c</mi></math>

이므로, $$ \frac{.. 2023. 12. 21.

이전 1 다음

티스토리툴바