Number Theory (Thailand Math POSN 2nd round)

Write a full solution

Theorems allowed to use: - Divisibility, gcd, lcm, Prime numbers - Modular arithmetic - Chinese Remainder Theorem - Complete Residue System modulo n - Reduced Residue System modulo n - Euler's Theorem - Fermat's Little Theorem - Wilson's Theorem

1.) Prove that there are no positive integers nn such that

2558n1(mod2000n1)2558^{n} \equiv 1 \pmod{2000^{n} - 1}

2.) Find the largest positive integer nn such that for all positive integersaa,

a9a(modn)a^{9} \equiv a \pmod{n}

3.) Find all solutions to linear congruence

2557x2015(mod1200)2557x \equiv 2015 \pmod{1200}

4.) Let pp be a prime number and N=10p19N = \displaystyle \frac{10^{p} - 1}{9}, prove that

N×108p+2N×107p+3N×106p++9N123456789(modp)N\times 10^{8p} + 2N\times 10^{7p} + 3N \times 10^{6p} + \dots + 9N \equiv 123456789 \pmod{p}

5.) Let pp be a prime number, prove that the congruence

x21(modp)x^{2} \equiv -1 \pmod{p}

has a solutions if and only if p=2p = 2 or p1(mod4)p \equiv 1 \pmod{4}.

This note is a part of Thailand Math POSN 2nd round 2015

Note by Samuraiwarm Tsunayoshi
6 years, 5 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


Sort by:

Top Newest

Solution to Q no 3 : 2557x=2015(mod 1200) Since gcd (2557,1200)=1 there is an unique solution (mod 1200) By using the Euclidean Algorithm to write 1 as the linear combination of 2557 and 1200, such as 1200×228-2557(-107)=1 here 2557(-107)=1(mod 1200) so, 2557(-107×2015)=2015 (mod 1200) Since , -107×2015 = 395 (mod 1200) We conclude that x=395 ( modulo 1200) is an unique solution . so x =395

Abdullah Ahmed - 5 years, 11 months ago

Log in to reply

Nice solution. Also this question can be done by the CRT

Shrihari B - 5 years, 9 months ago

Log in to reply

prob 1 : first assume there is a positive number n such that 2558^n =1 (mod 2000^n -1) or, 2558^n-1=0( mod 2000^n-1) that means 2000^n-1 divides 2558^n-1 now , let p be the maximum prime divisor of 2000^n -1 so. 2000^n=1(mod p) let this p be also a maximum prime divisor of 2558^n-1 so. 2558^n=1 (mod p) then , 2000^n =2558^n or 2000= 2558 and it is not possible . So there are no integer n such that 2558^n=1(mod 2000^n-1)

Abdullah Ahmed - 5 years, 11 months ago

Log in to reply

In your solution, it seems to me that you assume that anbn(modp)    a=ba^n\equiv b^n\pmod{p}\implies a=b where a,b,na,b,n are positive integers and pp is a prime. But that doesn't necessarily hold true.

Consider a=3,b=4,p=11,n=10a=3,b=4,p=11,n=10. We have aba\neq b but anbn(modp)a^n\equiv b^n\pmod{p}.

Prasun Biswas - 5 years, 11 months ago

Log in to reply

Solution to Q-4:

From Fermat's Little Theorem, we know that, for any integer aa and a prime pp, we have apa(modp)a^p\equiv a\pmod{p}. Then,

10p10(modp)    10p19(modp)    N=10p191(modp) ,p310^p\equiv 10\pmod{p}\implies 10^p-1\equiv 9\pmod{p}\implies N=\frac{10^p-1}{9}\equiv 1\pmod{p}~,p\neq 3

We have p3p\neq 3 in that case since gcd(9,3)=31\gcd(9,3)=3\neq 1 and 33 is the only prime that is not coprime to 99.

For p=3p=3, using divisibility rule of 33, we have N=10319=1110(mod3)N=\dfrac{10^3-1}{9}=111\equiv 0\pmod{3}. Hence, we combine these two results as (with prime pp),

N=10p19{1(modp) , p30(modp) , p=3  (i)N=\frac{10^p-1}{9}\equiv \begin{cases}1\pmod{p}~,~p\neq 3\\ 0\pmod{p}~,~p=3\end{cases}~\ldots~(i)

Trivial Observation 1: We note beforehand that 1234567890(mod3)123456789\equiv 0\pmod{3} using the divisibility rule of 33. As such, if we have x0(mod3)x\equiv 0\pmod{3}, we can also write that as x123456789(mod3)x\equiv 123456789\pmod{3} for any integer xx.

Now, for positive integral nn, 10nZ10^n\in\mathbb{Z} and hence, by FLT, we have 10np10n(modp)10^{np}\equiv 10^n\pmod{p} for all primes pp and positive integral nn. We use this result to form a modular congruence equation with the LHS of the statement to be proved modulo prime pp as,

LHSN(108+2×107+3×106++9)123456789N(modp)\textrm{LHS}\equiv N(10^8+2\times 10^7+3\times 10^6+\ldots +9)\equiv 123456789N\pmod{p}

Using (i)(i), this becomes,

LHS{123456789(modp) , p30(modp) , p=3\textrm{LHS}\equiv\begin{cases} 123456789\pmod{p}~,~p\neq 3\\ 0\pmod{p}~,~p=3\end{cases}

Using Trivial Observation 1, this becomes,

LHS123456789(modp)=RHS\textrm{LHS}\equiv 123456789\pmod{p}=\textrm{RHS}

N×108p+2N×107p+3N×106p++9N123456789(modp)\therefore\quad N\times 10^{8p} + 2N\times 10^{7p} + 3N \times 10^{6p} + \dots + 9N \equiv 123456789 \pmod{p}

Prasun Biswas - 6 years, 5 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...