Search

1.16: Divisibility Tests for 2, 3, 5, 9, 11
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.16%3A_Divisibility_Tests_for_2_3_5_9_11
Recall from Definition 4.2 that the decimal representation of the positive integer $a$ is given by $\label{eq:1} a=a_{n-1}a_{n-2}\dotsm a_1a_0$ when \[a=a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+\dotsb+a_1...Recall from Definition 4.2 that the decimal representation of the positive integer $a$ is given by $\label{eq:1} a=a_{n-1}a_{n-2}\dotsm a_1a_0$ when $a=a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+\dotsb+a_110+a_0\nonumber$ and $0\le a_i\le 9$ for $i=0,1,\dotsc,n-1$ .
1.14: Perfect Numbers and Mersenne Primes
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.14%3A_Perfect_Numbers_and_Mersenne_Primes
Since $q$ is odd, $\gcd(2^k,q)=1$ , so by Lemmas 13.1 and 13.2: $\sigma(n)=\sigma(2^k)\sigma(q)=(2^{k+1}-1)\sigma(q).\nonumber$ So we have \[2^{k+1}q=2n=\sigma(n)=(2^{k+1}-1)\sigma(q),\nonumber ...Since $q$ is odd, $\gcd(2^k,q)=1$ , so by Lemmas 13.1 and 13.2: $\sigma(n)=\sigma(2^k)\sigma(q)=(2^{k+1}-1)\sigma(q).\nonumber$ So we have $2^{k+1}q=2n=\sigma(n)=(2^{k+1}-1)\sigma(q),\nonumber$ hence $\label{eq:2} 2^{k+1}q=(2^{k+1}-1)\sigma(q).$ Now $\sigma^\ast(q)=\sigma(q)-q$ , so $\sigma(q)=\sigma^\ast(q)+q.\nonumber$ Putting this in $\eqref{eq:2}$ we get $2^{k+1}q=(2^{k+1}-1)(\sigma^\ast(q)+q)\nonumber$ or $2^{k+1}q=(2^{k+1}-1)\sigma^\ast(q)+2^{k+1}q-q\nonumber$ whic…
1.22: The Groups Um
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.22%3A_The_Groups_Um
A residue class $[a]\in\mathbb{Z}_m$ is called a unit if there is another residue class $[b]\in\mathbb{Z}_m$ such that $[a][b]=[1]$ . The set of all units in $\mathbb{Z}_m$ is denoted by \(U_m\...A residue class $[a]\in\mathbb{Z}_m$ is called a unit if there is another residue class $[b]\in\mathbb{Z}_m$ such that $[a][b]=[1]$ . The set of all units in $\mathbb{Z}_m$ is denoted by $U_m$ and is called the group of units of $\mathbb{Z}_m$ . Note that if $b\in B$ and $\gcd\left(b,p^n\right)=d>1$ , then $d$ is a factor of $p^n$ and $d>1$ so $d$ has $p$ as a factor.
1.27: The RSA Scheme
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.27%3A_The_RSA_Scheme
Now by Fermat’s Little Theorem, if $\gcd(x,p)=1$ we have $x^{p-1}\equiv 1\pmod p$ and raising both sides of the congruence to the power $(q-1)k$ we obtain: \[x^{(p-1)(q-1)k}\equiv 1\pmod p\nonum...Now by Fermat’s Little Theorem, if $\gcd(x,p)=1$ we have $x^{p-1}\equiv 1\pmod p$ and raising both sides of the congruence to the power $(q-1)k$ we obtain: $x^{(p-1)(q-1)k}\equiv 1\pmod p\nonumber$ and multiplying both sides by $x$ we have $x^{(p-1)(q-1)k+1}\equiv x\pmod p\nonumber$ That is, by $\eqref{eq:1}$ $\label{eq:2} x^{ed}\equiv x\pmod p.$ Now we proved $\eqref{eq:2}$ when $\gcd(x,p)=1$ , but if $\gcd(x,p)=p$ it is obvious since then $x\equiv 0\pmod p$ .
1.2: Proof by Induction
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.02%3A_Proof_by_Induction
Prove that if $a$ and $r$ are real numbers and $r\neq 1$ , then for $n \ge 1$ $a+ar+ar^2+\cdots +ar^n=\dfrac{a\left( r^{n+1}-1\right)}{r-1}.\nonumber$ This can be written as follows \[a(r^{n+...Prove that if $a$ and $r$ are real numbers and $r\neq 1$ , then for $n \ge 1$ $a+ar+ar^2+\cdots +ar^n=\dfrac{a\left( r^{n+1}-1\right)}{r-1}.\nonumber$ This can be written as follows $a(r^{n+1}-1) = (r-1)(a+ar+ar^2+\cdots +ar^n).\nonumber$ And important special case of which is $(r^{n+1}-1) = (r-1)(1+r+r^2+\cdots +r^n).\nonumber$
1.23: Two Theorems of Euler and Fermat
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.23%3A_Two_Theorems_of_Euler_and_Fermat
If $[a]\in U_m$ define $[a]^1=[a]$ and for $n>1$ , $[a]^n=[a][a]\dotsm[a]$ where there are $n$ copies of $[a]$ on the right. If $[a]\in U_m$ , then $[a]^n\in U_m$ for $n\ge 1$ and \([a...If $[a]\in U_m$ define $[a]^1=[a]$ and for $n>1$ , $[a]^n=[a][a]\dotsm[a]$ where there are $n$ copies of $[a]$ on the right. If $[a]\in U_m$ , then $[a]^n\in U_m$ for $n\ge 1$ and $[a]^n=[a^n]$ . Then $\begin{split} [a]^{k+1} &=[a]^k[a] \\ &=\left[a^k\right][a]\quad\text{by the induction hypothesis} \\ &=\left[a^ka\right]\quad\text{by Definition 21.1} \\ &=\left[a^{k+1}\right]\quad\text{since }a^ka=a^{k+1}. \end{split}$ So by the PMI, the theorem holds for $n\ge 1$ .
1.9: Blankinship's Method
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.09%3A_Blankinship's_Method
Let’s now consider a more complicated example: Take $a=1876$ , $b=365$ . $\begin{bmatrix} 1876 & 1 & 0 \\ 365 & 0 & 1 \end{bmatrix}\nonumber$ Now $1876=365\cdot5+51$ so we add $-5$ times the s...Let’s now consider a more complicated example: Take $a=1876$ , $b=365$ . $\begin{bmatrix} 1876 & 1 & 0 \\ 365 & 0 & 1 \end{bmatrix}\nonumber$ Now $1876=365\cdot5+51$ so we add $-5$ times the second row to the first row, getting: $\begin{bmatrix} 51 & 1 & -5 \\ 365 & 0 & 1 \end{bmatrix}\nonumber$ Now $365=51\cdot7+8$ , so we add $-7$ times row $1$ to row $2$ , getting: $\begin{bmatrix} 51 & 1 & -5 \\ 8 & -7 & 36 \end{bmatrix}\nonumber$ Now $51=8\cdot 6+3$ , so we add $-6$ ti…
1.1: Basic Axioms for Z
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.01%3A_Basic_Axioms_for_Z
If $a$ , $b\in\mathbb{Z}$ and $ab=1$ , then either $a=b=1$ or $a=b=-1$ . (Trichotomy) Given $a$ and $b$ , one and only one of the following holds: $a=b , \quad a<b , \quad b<a.\nonumber$
1.15: Congruences
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.15%3A_Congruences
Let $r=a\bmod m=b\bmod m$ , then by definition we have $a=mq_1+r,\quad 0\le r<m,\nonumber$ and $b=mq_2+r,\quad 0\le r<m.\nonumber$ Hence $a-b=m\left(q_1-q_2\right).\nonumber$ This shows that...Let $r=a\bmod m=b\bmod m$ , then by definition we have $a=mq_1+r,\quad 0\le r<m,\nonumber$ and $b=mq_2+r,\quad 0\le r<m.\nonumber$ Hence $a-b=m\left(q_1-q_2\right).\nonumber$ This shows that $m\mid a-b$ and hence $a\equiv b\pmod m$ , as desired.
Glossary
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/zz%3A_Back_Matter/02%3A_Glossary
1.24: Probabilistic Primality Tests
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Clark)/01%3A_Chapters/1.24%3A_Probabilistic_Primality_Tests
Thus, if $2<m\le 10^{10}$ and $m$ satisfies $2^{m-1}\equiv 1\pmod m$ , the probability $m$ is prime is $\frac{455,052,511}{455,052,511+14,884}\approx .999967292.\nonumber$ In other words, if...Thus, if $2<m\le 10^{10}$ and $m$ satisfies $2^{m-1}\equiv 1\pmod m$ , the probability $m$ is prime is $\frac{455,052,511}{455,052,511+14,884}\approx .999967292.\nonumber$ In other words, if you find that $2^{m-1}\equiv 1\pmod m$ , then it is highly likely (but not a certainty) that $m$ is prime, at least when $m\le 10^{10}$ . If $m>10^6$ and $a^{m-1}\equiv 1\pmod m$ for $a \in \{2,3,5,7,11,17,19,31,37,41\}$ , it is highly likely, but not certain, that $m$ is prime.

Search

Text Color

Text Size

Margin Size

Font Type

Support Center

How can we help?