\nModular Arithmetic, Primes and GCD, and Euclidean Algorithm

Readers will learn about Modular Arithmetic, Primes and GCD, and Euclidean Algorithm.

\nWhat is Modular Arithmetic

\nHow to find Primes and GCD

\nUnderstanding Euclidean Algorithm and its implementation in Java

",{"_241":242,"_38":39,"_42":43,"_40":41,"_61":62,"_243":244,"_288":239},"previewContent","

\n Introduction to Discrete Mathematics\n
- \n What is Discrete Mathematics\n
- \n What is the relationship between Discrete Mathematics and Computer Science\n
- \n Introducing necessary conceptions\n
\n
\n Introduction to Programming Languages\n
- \n Why these programming languages are discrete\n
- \n Introduction to objects\n
- \n What are discrete objects\n
\n
\n What is Algorithm\n
- \n Introduction to Algorithm\n
- \n Mission Critical Algorithm to get the best result in Computer Science\n
- \n How to implement Discrete Mathematical Algorithm in Java\n
\n
\n What is Data Structure and How it is related to Discrete Mathematical computations\n
\n
\n Set, Symmetric Difference and Propositional Logic\n
\n
\n Combinatorial Objects, Permutation and Combination, Combination with Repetition, and Pascal’s Triangle\n
\n
\n Rule of Sum and Products, Truth Tables, Logic Laws\n
- \n What are rule of sum and rule of products\n
- \n How to implement truth tables and conditionals in Java\n
- \n How to implement Logic Laws and Exclusive OR in Java\n
\n
\n Discrete Mathematical Functions and its Implementation\n
- \n What is function in Discrete Mathematics and how we can implement that concept in Java\n
- \n How to implement inverse of function and other functions that are present in Discrete Mathematics\n
\n
\n Modular Arithmetic, Primes and GCD, and Euclidean Algorithm\n
- \n What is Modular Arithmetic\n
- \n How to find Primes and GCD\n
- \n Understanding Euclidean Algorithm and its implementation in Java\n
\n
\n More on Algorithm and Data Structures in Java and how they are related to Discrete Mathematical conceptions\n
- \n More on Algorithm\n
- \n How to structure data in an efficient way\n
- \n More on Data Structures\n
\n
\n Appendix: Further reading and what is Next\n
\n

\nIntroduction to Discrete Mathematics

\n\n

What is Discrete Mathematics? We need to know that first. Second, we need to know what is the relationship of Discrete Mathematics to Computer Science. Finally, we want to know how we can implement the Discrete Mathematical concepts into various fields of Computer Science.

\n\n

Here, we are primarily concerned with Algorithm and Data Structure. These topics sit at the core of any Computer Science curriculum. Without understanding these two components properly, we can not claim that we are students of Computer Science!

\n\n

Therefore, I have chosen these two topics and try to implement Discrete Mathematical concepts into them so that our understanding might take a proper shape.\nIn this chapter, our first and foremost concern is to know what is Discrete Mathematics.

\n\n

\nWhat is Discrete Mathematics

Discrete Mathematics is a branch of Mathematics and, to be very particular, it is the study of Mathematical structures, and objects that are discrete.

\n\n

In that sense, ‘people’, ‘animal’, ‘chair’ and everything we see around us, fall under this mathematical study. Why? Because, they are discrete, distinct. They are not continuous. Think about real numbers that consist of rational and irrational numbers, or a number line, which is continuous; so that is not discrete mathematics. Rather, natural numbers (N), like 0, 1, 2, etc, which are discrete fall under this category.

\n\n

Discrete Mathematical conceptions handle with distinct and separated values. The opposite of discrete mathematics is continuous mathematics, such as calculus or Euclidean Geometry. However, Euclidean Algorithm that helps us find the greatest common divisor of two positive natural numbers (GCD), is very much discrete mathematics. We will see to an example in a minute.

\n\n

Have you found any contradiction in the above statement?

\n\n

I have found one; and before proceeding further, I think, we should make it clear first. We have just said that real numbers, or a number line where between 1 and 2, there are infinite numbers, cannot be discrete. However, when we say, positive natural numbers like 1, 2, 3, which are distinct and separated, belong to discrete mathematics. 1, 2 or 51, every positive natural numbers are also real numbers. Right? They belong to the number line. Right?\nThen where we stand? We are contradicting ourselves.

\n\n

Therefore, we can conclude that there is no exact definition of Discrete Mathematics. At best, we can say, that the opposite of continuous mathematics is discrete mathematics.

\n\n

In Mathematics, there are many things that are not continuous. You may think of Set theory, x co-ordinate and y co-ordinate, that refer to different positions on the quadrants, without joining them. You may think of GCD and LCM. Greatest common divisor and least common multiple. They are always discrete.

\n\n

Consider the statement in logic. True or False. They are discrete. Consider 0 and 1. The binary code, the core conceptions of Computer Science, they are very much discrete.

\n\n

Consider objects in any object-oriented-programming language. Every new object is discrete.

\n\n

That is why, Discrete Mathematical conceptions are closely related to every field of Computer Science. \nIn this book, we will only consider Algorithm and Data Structure part.

\n\n

In the following part we will compute the number of molecules in a hydrocarbon. First, we will compute this program using Java, after that, we will use C++ to compute the same program.

\n\n

Notice the algorithm. That is same for two languages, although syntactically there are differences. So the steps of algorithm varies. Let us see the algorithm first.

\n\n

The algorithm will be like this:

\n\n

1 Step 1: take input and store the mass of hydrocarbon, the number of carbon, and the \\\n2 number of hydrogen atoms\n3 Step 2: find and store the formula weight of one mole\n4 Step 3: find the number of molecules in given mass of hydrocarbon  using the above f\\\n5 ormula\n6 Step 4: output the stored input values and the result\n

\n\n\n\n

Considering that the algorithm is the same, suppose for both languages, its value is 1. However, the syntactical difference makes the second value change.

\n\n

If we consider that algorithm is the X axis, and the syntactical difference as Y axis, then the hypothetical value might be (1, 2) and (1, 5). Moreover, they are discrete, distinct and separated.

\n\n

If we want to connect them drawing a line, that no longer remains discrete. That becomes a continuous mathematical conceptions.

\n\n

With the help of these two programs, what I would like to point out is a simple mathematical statement. The difference between discrete mathematics and continuous mathematics is paper-thin. It also proves our definition of discrete mathematics. Anything, that is not continuous mathematics, is discrete mathematics.

\n\n

Let us see the Java program first.

\n\n

 1 //code 1.1\n 2 //Java\n 3     package fun.sanjibsinha.languagebasics;\n 4     /*\n 5     we will compute number of molecules in a hydrocarbon\n 6     a mole of any substance contains 6.02 * 10^23 molecules\n 7     this is called Avogadro's number\n 8     relationship of a mass of a substance and the number of molecules is:\n 9 \n10     molecules = mass * 1mole/FormulaWeight * (6.02 * 10^23 molecules)/i mole\n11     */\n12     import java.util.Scanner;\n13 \n14     public class HydroCarbonMolecule {\n15 \n16         static float massOfHydrocarbon = 0.00f;\n17         static int numberOfCarbonAtoms = 0;\n18         static int numberOfHydrogenAtoms = 0;\n19 \n20         public static void main(String[] args) {\n21 \n22             System.out.println(\"Enter mass of HydroCarbon in a floating point: \");\n23             Scanner mh = new Scanner(System.in);\n24             massOfHydrocarbon = mh.nextFloat();\n25             System.out.println(\"Enter the number of carbon atoms: \");\n26             Scanner nc = new Scanner(System.in);\n27             numberOfCarbonAtoms = nc.nextInt();\n28             System.out.println(\"Enter the number of hydrogen atoms: \");\n29             Scanner nh = new Scanner(System.in);\n30             numberOfHydrogenAtoms = nh.nextInt();\n31             final int CarbonAMU = 12;\n32             final int HydrogenAMU = 1;\n33             long formulaWeightOfOneMole = 111111111111L;\n34             formulaWeightOfOneMole = (numberOfCarbonAtoms * CarbonAMU)\n35                     + (numberOfHydrogenAtoms * HydrogenAMU);\n36             double AvogadroNumber = 6.02 * Math.pow(10, 23);\n37             double molecules = (massOfHydrocarbon/formulaWeightOfOneMole) * Avogadro\\\n38 Number;\n39             System.out.println(massOfHydrocarbon + \" grams of hydrocarbon with \" + n\\\n40 umberOfCarbonAtoms\n41             + \" carbon atoms and \" + numberOfHydrogenAtoms + \" hydrogen atoms contai\\\n42 n \"\n43             + molecules + \" molecules.\");\n44 \n45         }\n46     }\n

\n\n\n\n

Here goes the output:

\n\n

1 //output of code 1.1\n2 Enter mass of HydroCarbon in a floating point:\n3 16.00\n4 Enter the number of carbon atoms:\n5 1\n6 Enter the number of hydrogen atoms:\n7 4\n8 16.0 grams of hydrocarbon with\n9 1 carbon atoms and 4 hydrogen atoms contain 6.019999999999999E23 molecules.\n

\n\n\n\n

I would like to write the Avogadro’s number using the scientific notation this way:

\n\n

1 double AvogadroNumber = 6.02e23;\n

\n\n\n\n

The output changes from 6.019999999999999E23 to 6.02E23, although it should not have mattered how you have written the Avogadro’s number. In the first case,

\n\n

I have used the Java pow() method. In the second case,I have used the scientific notation. However, the outputs are discrete.

\n\n

I would like to show you the same program in C++, where I have used the ‘cmath’ library’s pow() function, the same way I have used pow() method in my Java code.

\n\n

Let us see the program first.

\n\n

 1 //code 1.2\n 2 //C++\n 3 #include <iostream>\n 4 #include <string>\n 5 #include <cmath>\n 6 \n 7 using namespace std;\n 8 \n 9 int main() {\n10 /* code */\n11 std::cout << \"Enter mass of hydrocarbon in decimal point value, like 2.33\" << '\\n';\n12 float massOfHydrocarbon;\n13 std::cin >> massOfHydrocarbon;\n14 std::cout << \"Enter number of carbon atoms in positive integer, like 2\" << '\\n';\n15 int numberOfCarbonAtoms;\n16 std::cin >> numberOfCarbonAtoms;\n17 std::cout << \"Enter the number of hydrogen atoms in positive integer, like 3\" << '\\n\\\n18 ';\n19 int numberOfHydrogenAtoms;\n20 std::cin >> numberOfHydrogenAtoms;\n21 const int carbonAMU = 12;\n22 const int hydrogenAMU = 1;\n23 long formulaWeightOfOneMole = (numberOfCarbonAtoms * carbonAMU) + (numberOfHydrogenA\\\n24 toms * hydrogenAMU);\n25 const double AvogadroNumber = 6.02 * pow(10, 23);\n26 double moleculesInHydrocarbon = (massOfHydrocarbon / formulaWeightOfOneMole) * Avoga\\\n27 droNumber;\n28 std::cout << massOfHydrocarbon << \" grams of hydrocarbon with \" << numberOfCarbonAto\\\n29 ms <<\n30 \" \\ncarbon atoms and \" << numberOfHydrogenAtoms << \" hydrogen atoms contain \" << mol\\\n31 eculesInHydrocarbon;\n32 return 0;\n33 }\n

\n\n\n\n

The output is: 6.02e+23. Now, if we change the Avogadro’s number to this:

\n\n

1 const double AvogadroNumber = 6.02e23;\n

\n\n\n\n

The output remains the same. In Java, although the value changes.

\n\n

Now, we can conclude that every programming language is discrete, not only syntactically, but also in their output.

\n\n

\nWhat is the relationship between Discrete Mathematics and Computer Science

We can now understand how discrete mathematics and computer science are related. Through our programming logic and algorithm, we can reproduce continuous mathematics in any programming language, like Java.

\n\n

Let us see another example in Java.

\n\n

First the code, then we will discuss the concept.

\n\n

 1 //code 1.3\n 2 //Java\n 3 package fun.sanjibsinha;\n 4 \n 5 import java.util.Scanner;\n 6 \n 7 /*\n 8 Finding the y-coordinate of a point on a line\n 9 where x-coordinate is given\n10 */\n11 public class FindingYCoordinate {\n12 \n13     static int lineSlope = 0;\n14     static int yIntercept = 0;\n15     static int xCoordinate = 0;\n16     static int yCoordinate = 0;\n17 \n18     public static void main(String[] args) {\n19 \n20         System.out.println(\"Enter the value of the line-slope in positive integer: \"\\\n21 );\n22         Scanner slopeOfLine = new Scanner(System.in);\n23         lineSlope = slopeOfLine.nextInt();\n24         System.out.println(\"Enter the intercept of y-axis: \");\n25         Scanner interceptOfY = new Scanner(System.in);\n26         yIntercept = interceptOfY.nextInt();\n27         System.out.println(\"Enter the value of x-coordinate: \");\n28         Scanner coordinateOfX = new Scanner(System.in);\n29         xCoordinate = coordinateOfX.nextInt();\n30         yCoordinate = lineSlope * xCoordinate + yIntercept;\n31         //line of slope = rise vertically/run horizontally\n32         //yCoordinate = (lineSlope * xCoordinate) + yIntercept;\n33         System.out.println(\"The y-coordinate is: \" + yCoordinate + \". When the slope\\\n34  of line is: \"\n35                 + lineSlope + \". Intercept of y-axis is: \" + yIntercept + \". X coord\\\n36 inate is: \" + xCoordinate);\n37 \n38     }\n39 \n40 }\n

\n\n\n\n

In the above code, with the help of line-slope and y-intercept, we find the y-coordinate. The value of x-coordinate is given.

\n\n

A line-slope is the ratio of vertical rise and horizontal run of the line. The y-intercept is a given point on the y axis. If we run the program and provide the values, the output comes out as:

\n\n

1 //output of code 1.3\n2 Enter the value of the line-slope in positive integer: \n3 6\n4 Enter the intercept of y-axis: \n5 2\n6 Enter the value of x-coordinate: \n7 2\n8 The y-coordinate is: 14. When the slope of line is: 6. Intercept of y-axis is: 2. X \\\n9 coordinate is: 2\n

\n\n\n\n

In the above output it is evident that every number is discrete and computing them is easier with the help of a formula. Here the value of y-coordinate is 14, when x-coordinate is 2.

\n\n

What makes discrete mathematics different from the continuous mathematical proceedings is its capacity of getting counted, discrete structures are always either countable, or distinct. In the above code, we have seen that each vertical rise and horizontal run are discrete, distinct from others. Each time you run the code, providing distinct values will give you values that are separable from the previous ones.

\n\n

\nIntroducing necessary conceptions

In the following chapters, we will see plenty of examples where discrete mathematical computations will be used.

\n\n

To name a few, we will discuss set theory and its implementations in data structures. We will see how permutation and combination work together in algorithm. The role of logical statement or truth table will play a great role in our discussion.

\n\n

We will see how finite collections of discrete objects are implemented in the data structures. They can not only be counted, but also arranged and placed into sets. Studying Euclidean algorithm, along with finding the GCD and LCM, will be a major part in our discussion.

\n\n

There are many interesting topics to come. So stay tuned and keep reading on.

\n\n\n

\nIntroduction to Programming Languages

\n\n

Here are some quick Markdown examples to get you started.

\n\n

To start a new paragraph, hit the return key twice. You want to create a blank line between paragraphs.

\n\n

To italicize, surround a word in asterisks.

\n\n

To bold, use two asterisks.

\n\n

Here is a link to the leanpub home-page.

\n\n

Chapter 3 tells you how to make a preview of your book.

\n\n

\nWhy these programming languages are discrete

\n\n

\nIntroduction to objects

\n\n

\nWhat are discrete objects

\n\n\n

\nWhat is Algorithm

\n\n

To make a preview of your book, click on the “Preview” button on the left. We’ll show you some links to download your book when the preview is complete.

\n\n

You can keep writing in the meantime.

\n\n

That’s it for the brief introduction to Leanpub.

\n\n

This section will show readers additional Discrete Mathematical conceptions that are necessary to understand Algorithm and Data Structures

\n\n

\nSequence and Series

\n\n

\nHow we can use Sequence and Series to structure our Data

\n\n

\nWhat could be the next challenges to learn more about the relationship between Discrete Mathematical conceptions and Algorithm as well as Date Structures

\n\n

\n\n","tocStructure",[245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287],{"_72":73,"_38":74,"_66":-5,"_75":76,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":82,"_66":-5,"_75":83,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":88,"_66":-5,"_75":89,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":91,"_66":-5,"_75":92,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":94,"_66":-5,"_75":95,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":98,"_66":-5,"_75":99,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":101,"_66":-5,"_75":102,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":104,"_66":-5,"_75":105,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":107,"_66":-5,"_75":108,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":111,"_66":-5,"_75":112,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":114,"_66":-5,"_75":115,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":117,"_66":-5,"_75":118,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":120,"_66":-5,"_75":121,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":124,"_66":-5,"_75":125,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":127,"_66":-5,"_75":128,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":130,"_66":-5,"_75":131,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":133,"_66":-5,"_75":134,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":137,"_66":-5,"_75":138,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":140,"_66":-5,"_75":141,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":143,"_66":-5,"_75":144,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":146,"_66":-5,"_75":147,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":150,"_66":-5,"_75":151,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":153,"_66":-5,"_75":154,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":156,"_66":-5,"_75":157,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":159,"_66":-5,"_75":160,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":163,"_66":-5,"_75":164,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":166,"_66":-5,"_75":167,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":169,"_66":-5,"_75":170,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":172,"_66":-5,"_75":173,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":176,"_66":-5,"_75":177,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":179,"_66":-5,"_75":180,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":182,"_66":-5,"_75":183,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":186,"_66":-5,"_75":187,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":189,"_66":-5,"_75":190,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":192,"_66":-5,"_75":193,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":195,"_66":-5,"_75":196,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":199,"_66":-5,"_75":200,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":202,"_66":-5,"_75":203,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":205,"_66":-5,"_75":206,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":73,"_38":208,"_66":-5,"_75":209,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":212,"_66":-5,"_75":213,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":215,"_66":-5,"_75":216,"_68":77,"_84":-5,"_85":-5,"_86":-5},{"_72":81,"_38":218,"_66":-5,"_75":219,"_68":77,"_84":-5,"_85":-5,"_86":-5},"publicChapterContent","nextChapter","sections",[277,278,279],"routes/_store+/_layout","routes/_store+/_readers+/_layout","actionData","errors"]

\nModular Arithmetic, Primes and GCD, and Euclidean Algorithm

\nWhat is Modular Arithmetic

\nHow to find Primes and GCD

\nUnderstanding Euclidean Algorithm and its implementation in Java

Table of Contents

\nIntroduction to Discrete Mathematics

\nWhat is Discrete Mathematics

\nWhat is the relationship between Discrete Mathematics and Computer Science

\nIntroducing necessary conceptions

\nIntroduction to Programming Languages

\nWhy these programming languages are discrete

\nIntroduction to objects

\nWhat are discrete objects

\nWhat is Algorithm

\nIntroduction to Algorithm

\nMission Critical Algorithm to get the best result in Computer Science

\nHow to implement Discrete Mathematical Algorithm in Java

\nWhat is Data Structure and How it is related to Discrete Mathematical computations

\nWhat is Data Structures and why we need to learn it

\nHow we can implement Discrete Mathematical conceptions in understanding Data Structures

\nWhat are the different types of Data Structures used in C++, Java, Python, Dart and C

\nSet, Symmetric Difference and Propositional Logic

\nWhat is Set in Discrete Mathematics and how it is implemented in Java Data Structures

\nHow we can find symmetric difference in Java

\nHow to implement propositional logic in Java

\nCombinatorial Objects, Permutation and Combination, Combination with Repetition, and Pascal’s Triangle

\nWhat is Combinatorial object, permutation and combination and how we can implement that concepts with the help of Java

\nWhat is combinations with repetition and how it can be implemented

\nHow we can implement Pascal’s Triangle in Java

\nRule of Sum and Products, Truth Tables, Logic Laws

\nWhat are rule of sum and rule of products

\nHow to implement truth tables and conditionals in Java

\nHow to implement Logic Laws and Exclusive OR in Java

\nDiscrete Mathematical Functions and its Implementation

\nWhat is function in Discrete Mathematics and how we can implement that concept in Java

\nHow to implement inverse of function and other functions that are present in Discrete Mathematics

\nModular Arithmetic, Primes and GCD, and Euclidean Algorithm

\nWhat is Modular Arithmetic

\nHow to find Primes and GCD

\nUnderstanding Euclidean Algorithm and its implementation in Java

\nMore on Algorithm and Data Structures in Java and how they are related to Discrete Mathematical conceptions

\nMore on Algorithm

\nHow to structure data in an efficient way

\nMore on Data Structures

\nAppendix: Further reading and what is Next

\nSequence and Series

\nHow we can use Sequence and Series to structure our Data

\nWhat could be the next challenges to learn more about the relationship between Discrete Mathematical conceptions and Algorithm as well as Date Structures