# introduction to number theory

}\) Thus, \begin{equation*} \begin{aligned}84x - 38 \amp \equiv 79 \pmod{15} \\ 9x - 8 \amp \equiv 4 \pmod{15} \\ 9x \amp \equiv 12 \pmod{15} \\ 9x \amp \equiv 72 \pmod{15}. With all this in mind, let's introduce some notation. If we want to claim that $$n/m$$ is not an integer, so $$m$$ does not divide $$n\text{,}$$ then we can write $$m \nmid n\text{.}$$. This would be going too far, so we will refuse this option. Thus we get the remainder class, There are three more to go. We have $$84 \equiv 9\text{,}$$ $$38 \equiv 8$$ and $$79 \equiv 4\text{. \( \def\sat{\mbox{Sat}}$$ Notice we also include negative integers. The explanations are very clear. $$\def\circleA{(-.5,0) circle (1)}$$ }\) In other words, if $$b \mid a\text{,}$$ then $$a = bk$$ for some integer $$k$$ (this is saying $$a$$ is some multiple of $$b$$). $$\def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}$$ 2, 2008. To get the free app, enter your mobile phone number. }\) This gives 2, 5, 8, 11, and 14 respectively, for which only 14 is congruent to 4. $$\def\B{\mathbf{B}}$$ }\) In other words, we have $$ad = bd + kn$$ for some integer $$k\text{. This gives. True. Try 83: Is this the best we can do? We could now divide both sides by 3, or try to increase 9 by a multiple of 14 to get a multiple of 6. \( \def\iffmodels{\bmodels\models}$$ 46, No. Historically, number theory was known as the Queen of Mathematics and was very much a branch of pure mathematics, studied for its own sake instead of as a means to understanding real world applications. We will especially want to study therelationshipsbetween different sorts of numbers. $$\def\VVee{\d\Vee\mkern-18mu\Vee}$$ $$\def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}$$ $$\def\F{\mathbb F}$$ Consider what we get when we take the difference of $$a$$ and $$b\text{:}$$, So $$a-b$$ is a multiple of $$n\text{,}$$ or equivalently, $$n \mid a-b\text{.}$$. It is easy to add and multiply natural numbers. What mathematical discoveries can we make about the natural numbers themselves? }\) Here we are looking for all the numbers divisible by $$5$$ since $$a = 5q+0\text{. }$$ Which integers, when divided by 5, have remainder 1? $$\def\circleC{(0,-1) circle (1)}$$ True. Specifically, we could prove that congruence modulo $$n$$ is an equivalence relation, which would require checking the following three facts: Congruence Modulo $$n$$ is an Equivalence Relation. In other words, even if $$ad \equiv bd \pmod n\text{,}$$ we do not know that $$a \equiv b \pmod n\text{. }$$ If $$k = -2\text{,}$$ we get $$(57, -32)\text{.}$$. Instead, our system considers things like how recent a review is and if the reviewer bought the item on Amazon. }\) The rest of the factors of $$d$$ will come from $$k\text{,}$$ no problem. For each $$k\text{,}$$ $$x = -1-29k$$ and $$y = 2 + 17k$$ will satisfy the equation. $$\def\Th{\mbox{Th}}$$ The above fact helps with this. Recall in our study of induction, we asked: Which amounts of postage can be made exactly using just 5-cent and 8-cent stamps? We might try multiplying $$m$$ by larger and larger numbers until we get close to $$n\text{. For example, suppose you need to solve. We have used the natural numbers to solve problems. }$$ That means $$a = b + kn$$ and $$c = d + jn$$ for integers $$k$$ and $$j\text{. Both 8 and 12 are divisible by 4, but this does not mean that \(12$$ is divisible by $$8\text{. }$$ Rearranging that equation, we get $$a = b + kn\text{. Suppose \(a \equiv b \pmod{n}$$ and $$c \equiv d \pmod{n}\text{. \draw (\x,\y) node{#3}; }$$ Of course $$90 \equiv 0 \pmod 9\text{,}$$ so we can replace the 90 in the sum with 0. Published October 2005,February 2011. 1 divides every number (other than 0). $$\def\entry{\entry}$$ }\) This conforms with our earlier observation that all the numbers in a particular remainder class are the same amount larger than the multiples of $$n\text{. this is one best book for mathematical baground for cryptography. 3 This works for 3 as well, but definitely not for any modulus in general. A solution to a Diophantine equation is a solution to the equation consisting only of integers. }$$ So which definition is correct? In other words, we have found that, Since $$13 < 1642\text{,}$$ we can now safely say that $$1642 \nmid 136299\text{.}$$. What if we had 2-cent and 4-cent stamps. }\), $$\renewcommand{\bar}{\overline}$$ }\), This is no surprise. }\), If $$d$$ and $$n$$ have no common factors then $$\gcd(d,n) = 1\text{,}$$ so $$a \equiv b \pmod n\text{. By Mathew Crawford A thorough introduction for students in grades 7-10 to topics in number theory such as primes & composites, multiples & divisors, prime factorization and its uses, base numbers, modular arithmetic, divisibility rules, linear congruences, how to develop number sense, and more. \( \def\iff{\leftrightarrow}$$ If two numbers belong to the same remainder class, then in some way, they are the same. The division algorithm tells us that there are only b possible remainders when dividing by b. Probably the most well known example of this is RSA cryptography, one of the methods used in encrypt data on the internet. \begin{equation*} 3^{123} = 27^{41} \equiv 6^{41} \pmod 7, \end{equation*}. }\) Really, we just need to check whether $$\gcd(51, 87) \mid 123\text{. \( \def\circleA{(-.5,0) circle (1)}$$ You should take a minute to convince yourself that each of the properties above actually hold of congruence. \end{equation*}, \begin{equation*} \begin{aligned}8y \amp \equiv 367 \pmod{5}\\ 3y \amp \equiv 2 \pmod 5\\ 3y \amp \equiv 12 \pmod 5\\ y \amp \equiv 4 \pmod 5.\\ \end{aligned} \end{equation*}. Discrete math deals with whole numbers of things. $$\def\entry{\entry}$$ It also analyzes reviews to verify trustworthiness. In each case we can create one more cent of postage. You might wonder what would happen if we changed the denomination of the stamps. You could keep adding 51 to the right side until you get a multiple of 13: You would get 57, 108, 159, 210, 261, 312, and 312 is the first of these that is divisible by 13. $$\def\Gal{\mbox{Gal}}$$ $$\newcommand{\gt}{>;}$$ In fact, we now know something more: any number is congruent to the sum of its digits, modulo 9. '―L’Enseignement Mathématique, Vol. Thus we can safely write. In general, solving Diophantine equations is hard (in fact, there is provably no general algorithm for deciding whether a Diophantine equation has a solution, a result known as Matiyasevich's Theorem). Next, consider how congruence behaves when doing basic arithmetic. Let's work this particular example to see how this might go. So we can in fact replace the 400 with simply a 4. So in this example, simply compute $$3x + 2$$ for values of $$x \in \{0,1,2,3,4\}\text{. Find the remainder when \(3^{123}$$ is divided by 7. That is, they are the same up to division by $$b$$. Think of congruence as being “basically equal.” If we have two numbers which are basically equal, and we add basically the same thing to both sides, the result will be basically equal. The other two facts can be proved in a similar way. This helps us understand the structure of the natural numbers and opens the door to many interesting questions and applications. }\) We cannot divide $$8$$ by 6, but we can divide 8 by the greatest common factor of $$8$$ and $$6\text{. Is it really true? The technical way to say this is that the remainder classes modulo \(b$$ form a partition of the integers. For example, is there a value of $$x$$ that satisfies. Of course this is true as well, it is the special case where $$c = d\text{. This will allow us to reduce the congruence to just one variable. Probably the most famous example of a Diophantine equation is \(a^2 + b^2 = c^2\text{. Of course then we could observe that. This last example raises a question: how might one decide whether \(m \mid n\text{? We could have also moved to a congruence modulo 29, although there is usually a good reason to select the smaller choice, as this will allow us to reduce the other coefficient. In this example, since the modulus is small, we could simply try every possible value for \(x\text{. A more common technique would be to apply the Euclidean algorithm. In our case, we reduce the congruence as follows: Now at this point we know \(y = 2 + 17k$$ will work for any integer $$k\text{. Here \(12 = -3 \cdot 4\text{. This is the main question of number theory: a huge, ancient, complex, and above all, beautiful branch of mathematics. What if we add something congruent to 1 to something congruent to 2? This seems reasonable. Please try again. There was a problem loading your book clubs. Fourth Edition – ISBN: 978-0-321-81619-1 – © 2012 Pearson Education, Inc. A … Let's also see how you could solve this using our rules for the algebra of congruences. When \(k = 15\text{,}$$ we have $$x = 1$$ and $$y = 79\text{. Here, when \(x = 4$$ we get $$3x + 2 = 14$$ which is indeed congruent to 4 modulo 5. While we don't really know how to divide, we do know how to multiply. It would be wrong to say \(8 = 23\text{. There was an error retrieving your Wish Lists. We could have seen this immediately in fact. Thus there are no solutions to the congruence. If we take some number of 2-cent stamps and some number of 4-cent stamps, what can we say about the total? This clear presentation covers the elements of number theory, with stress on the basic topics concerning prime numbers and Diophantine equations (especially quadratic equations in two variables).