Online Course Discussion Forum

Questions on Math Challenge II-A Number Theory

 
 
Picture of Tina Jin
Questions on Math Challenge II-A Number Theory
by Tina Jin - Wednesday, 29 December 2021, 9:22 PM
 
Hello. Here are some questions I have for the Number Theory Lectures:


2.28: I have checked the solutions on the quiz, but I don't get this part:

gcd(b,a)=gcd(ba,a)=gcd(b2a,a)==gcd(bqa,a)=gcd(r,a)gcd(b,a)=gcd(b−a,a)=gcd(b−2a,a)=⋯=gcd(b−qa,a)=gcd(r,a)
How can the gcd(b-a,a) become gcd(b-2a,a)? 

3.10: Mr. David didn't explain this problem, so I tried it on my own, but I got stuck after slipping (am+bn)/n *nCm.

4.5: I still don't get the solution to the problem the teacher showed...

4.25 and 4.26: ???

5.22: I don't know how to prove it.

6.1: b) I don't get how to get from b^k≡a^(-k) (mod m) to a^k*a^(-k)≡a^(k-k)≡a^0≡1(mod m) 

Where did the b^k go?

6.7, 6.9, 6.10, 6.29, 6.30: I don't really get it...

7.28: I got stuck after trying to look at the LCMs and stuff...

7.30: Can you give me a hint?

8.6: How do I want to factor as (x-p)(y+p), HENCE (x-p)(y+p)=(-p)^2 I don't get how to get from  (x-p)(y+p) to (x-p)(y+p)=(-p)^2.

8.8: I tried to do it, but I don't know how.

8.15: The solution for 8.14 is 3, so how is it congruence mod 5?

8.23: I got stuck

9.26: Shouldn't the answer be all integers?

10.8:  how did the teacher get it to be 4?


Super sorry for the long list! For all these problems, I feel like I'm almost there, but I don't get how to do it. Thank you so much!!



 
Picture of John Lensmire
Re: Questions on Math Challenge II-A Number Theory
by John Lensmire - Friday, 14 January 2022, 2:34 PM
 

I'll answer a few chapters at a time.

For 2.28, part (a) is using the result proven in 2.8 that gcd(Y,X) = gcd(Y-X, X) over and over.

  • Start with Y = b and X = a to get gcd(b,a) = gcd(b-a, a).
  • Next let Y = b-a and X = a to get gcd(b-a, a) = gcd(b-a - a, a) = gcd(b-2a, a).
  • Then let Y = b-2a and X = a to get gcd(b-2a, a) = gcd(b-2a-a, a) = gcd(b-3a, a), etc.

However, if b = a*q + r, this means that for some integer q, we have b-a*q = r. Hence, repeating the above steps over and over gives you that gcd(b, a) = gcd(r,a) as needed.

For example, to show gcd(17,5) = gcd(5,2) we'd have$$\gcd(17,5) = \gcd(12, 5) = \gcd(7,5) = \gcd(2,5)$$by subtracting 5 from 17 over and over.

For 3.10, the only real step that is using Number Theory is the first where you replace $\gcd(m,n) = am+bn$ for integers $a$ and $b$ (which is guaranteed by Bezout's identity). The rest of the steps are just algebraic manipulations to simplify$$\frac{am+bn}{n}\cdot \binom{n}{m} \text{ to } a\binom{n-1}{m-1} + b\binom{n}{m}.$$Why do we care about this simplification? Well we know that both of the expressions $\binom{n-1}{m-1}$ and $\binom{n}{m}$ are integers, so then the whole thing is also an integer like we need.

Hope this helps!

Picture of John Lensmire
Re: Questions on Math Challenge II-A Number Theory
by John Lensmire - Wednesday, 19 January 2022, 3:28 PM
 

For Chapter 4 let's look at a separate example that combines some of your questions. Let's look at $n = 21212$ and ask, (a) what is the remainder when $n$ is divided by $9$?, (b) what is the remainder when $n$ is divided by $3$?, and (c) what is the remainder when $n$ is divided by $11$?

For all of these questions we can start with place values. Note$$n=21212 = 2\cdot 10000 + 1\cdot 1000 + 2\cdot 100 + 1\cdot 10 + 2\cdot 1.$$

Let's start by looking at this $\pmod{9}$. Remember that when working with mods, we can take remainders of each term separately. Note that$$10000\equiv 1000\equiv 100\equiv 10\equiv 1 \pmod{9},$$so $$\begin{aligned} n &= 2\cdot 10000 + 1\cdot 1000 + 2\cdot 100 + 1\cdot 10 + 2\cdot 1 \\ &\equiv 2\cdot 1 + 1\cdot 1 + 2\cdot 1 + 1\cdot 1 + 2\cdot 1 \pmod{9} \\ &\equiv 2+1+2+1+2 \pmod{9} \end{aligned}$$ Hence $n$ is equivalent to the sum of its digits mod 9, so $n\equiv 8 \pmod{9}$.

For (b), note the above still all holds with $3$ in place of $9$. Hence, $n\equiv 8\equiv 2 \pmod{3}$ and the remainder when $n$ is divided by $3$ is $2$.

For (c), things are a little different when we divide by $11$. Here, $$10000\equiv 100\equiv 1 \pmod{11} \text{ and } 1000\equiv 10\equiv -1 \pmod{11}.$$ Therefore, $$\begin{aligned} n &= 2\cdot 10000 + 1\cdot 1000 + 2\cdot 100 + 1\cdot 10 + 2\cdot 1 \\ &\equiv 2\cdot 1 + 1\cdot -1 + 2\cdot 1 + 1\cdot -1 + 2\cdot 1 \pmod{11} \\ &\equiv 2-1+2-1+2 \pmod{9} \end{aligned}$$ so $n\equiv 4\pmod{11}$ (the alternating sum of its digits).

Hopefully these examples give some ideas on how to approach 4.5, 4.25, and 4.26.

Picture of John Lensmire
Re: Questions on Math Challenge II-A Number Theory
by John Lensmire - Thursday, 20 January 2022, 1:20 PM
 

For Chapters 5 and 6, first off don't worry too much about the proof in 5.22 or the problems 6.10 and 6.30. Those are a little more advanced and abstract and I'd say they are lower priority. We can come back to them if you want after all the others are understood.

For 6.1 part b), let's look at an example to follow along with the proof. Let's let $a=3$ and $p=11$ and we want to show that there's a value of $K$ such that $3^K\equiv 1\pmod{11}$. Let's look at a table of values of $3^k\pmod{11}$. $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline 3^k \pmod{11} & 3 & 9 & 5 & 4 & 1 & 3 & 9 & 5 & 4 & 1 & 3 & 9 \\ \hline \end{array}$$ As a side note, we've listed 12 values here because there are only 11 possible remainders when we divide by 11. Therefore, even if we didn't know the values of $3^k\pmod{11}$, we are guaranteed to have SOME repeat here. (This is the main argument in part (a)).

Now, with this chart it's clear to see that $K=5$ works. However, let's show how we can use one of the other repeated values into what we want.

For example, suppose you notice that $3^3 \equiv 3^8\pmod{11}$ as your repeated value. How can we turn this into $3^5\equiv 1 \pmod{11}$? Since $\gcd(3,11) = 1$, we know that $3$ has a multiplicative inverse mod 11, denoted by $b$ in the solution. Note that $b=4$ works as $4\cdot 3 = 12\equiv 1\pmod{11}$. Thus, $$\begin{aligned} 3^3&\equiv 3^8 \pmod{11} \\ \Rightarrow 4\cdot 3^3&\equiv 4\cdot 3^8\pmod{11} \\ \Rightarrow (4\cdot 3)\cdot 3^2 &\equiv (4\cdot 3)\cdot 3^7 \pmod{11} \\ \Rightarrow 3^2 & \equiv 3^7 \pmod{11} \end{aligned}$$ Note that $b=4$ cancels out one of the powers of $3$ on each side.

Repeating this two more times gives $3^1\equiv 3^6\pmod{11}$ and then $1\equiv 3^5\pmod{11}$ as needed. The $b^k$ in the proof is just denoting this canceling that is taking place with the mult. inverse mod 11.

Picture of John Lensmire
Re: Questions on Math Challenge II-A Number Theory
by John Lensmire - Friday, 18 February 2022, 10:42 AM
 

For 6.7, let's look at a smaller example to see if we can find a pattern.

Suppose we have the same recursive definition, except now we want to just find $a_4$. This is small enough that we can write out the definition (even if it is messy): $$a_4 = 3^{a_3} = 3^{\displaystyle 3^{a_2}} = 3^{\displaystyle 3^{\displaystyle 3^{a_1}}} = 3^{\displaystyle 3^{\displaystyle 3^{1}}}$$ Now, let's ignore the fact that these numbers are small enough to calculate directly to try to see how we could approach the problem in general.

Using patterns or Fermat's Little Theorem, we know that $3^6\equiv 1 \pmod{7}$. Therefore, we know that only the remainder when we divide by $6$ matters for the exponent when we are working mod 7. We can write: $$3^{\displaystyle 3^{\displaystyle 3^{1}}} \equiv \displaystyle 3^{\displaystyle 3^{\displaystyle 3^{1}}\pmod{6}} \pmod{7}.$$ So we need to find the remainder when $3^{\displaystyle 3^{1}}$ is divided by $6$. Is there a pattern in the powers of $3$ working mod 6?

Picture of Tina Jin
Re: Questions on Math Challenge II-A Number Theory
by Tina Jin - Tuesday, 1 February 2022, 4:15 PM
 

Thank you so much! I know it was a lot of problems, and thank you for replying to them! Thank you again!