Belajar Matematika Online

PERHATIAN: Mohon maaf, jika ada tampilan iklan atau iklan yang tidak baik, jangan diteruskan! Kami akan melakukan upaya pemblokiran, terima kasih!
Tampilkan postingan dengan label Number Theory. Tampilkan semua postingan
Tampilkan postingan dengan label Number Theory. Tampilkan semua postingan

Some Conjecture of Prima Number

Several other theorems were proved concerning prime numbers. many great mathematicians approached problems that are related to primes. There are still many open problems of which we will mention some.

Conjecture 1. Twin Prime Conjecture There are in?nitely many pairs primes p and p + 2.

Conjecture 2. Goldbach's Conjecture Every even positive integer greater than 2 can be written as the sum of two primes.

Conjecture 3. The n2 + 1 Conjecture There are in?nitely many primes of the form n2 + 1, where n is a positive integer.

Conjecture 4. Polignac Conjecture For every even number 2n are there infinitely many pairs of consecutive primes which differ by 2n.



Conjecture 5. Opperman Conjecture Is there always a prime between n^2 and
(n + 1)^2?

The Function [x]

Definition 1. The function [x] represents the largest integer not exceeding x. In other words, for real x, [x] is the unique integer such that x - 1 < [x] </= x < [x] + 1.

We also define ((x)) to be the fractional part of x. In other words ((x)) =x - [x]. We now list some properties of [x] that will be used in later or in more advanced courses in number theory.
1. [x + n] = [x] + n, if n is an integer.
2. [x] + [y] </= [x + y].
3. [x] + [-x] is 0 if x is an integer and -1 otherwise.
4. The number of integers m for which x < m </= y is [y] - [x].
5. The number of multiples of m which do not exceed x is [x/m].


Using the de?nition of [x], it will be easy to see that the above properties are direct consequences of the definition. We now define some symbols that will be used to estimate the growth of number theoretic functions. These symbols will be not be really appreciated in the context of this book but these are often used in many analytic proofs.

Linear Diophantine Equations

In this section, we discuss equations in two variables called diophantine equations. These kinds of equations require integer solutions. The goal of this section is to present the set of points that determine the solution to this kind of equations. Geo-metrically speaking, the diophantine equation represent the equation of a straight line. We need to ?nd the points whose coordinates are integers and through which the straight line passes.

Definition 1. A linear equation of the form ax + by = c where a, b and c are integers is known as a linear diophantine equation. Note that a solution to the linear diophantine equation ($x_0, y_0$) requires $x_0$ and $y_0$ to be integers. The following theorem describes the case in which the diophantine equation has a solution and what are the solutions of such equations.

Theorem 1. The equation ax + by = c has integer solutions if and only if d | c where d = (a, b). If the equation has one solution x = x_0, y = y_0, then there are infinitely many solutions and the solutions are given by 
x = x_0 + (b/d)t 

y = y_0 - (a/d)t
 

where t is an arbitrary integer.


Proof. Suppose that the equation ax + by = c has integer solution x and y. Thus since d | a and
 d | b, then d | (ax + by) = c. Now we have to prove that if d | c, then the equation has integral solution. Assume that d | c. By theorem 3 (GCD), there exist integers m and n such that

d = am + bn. And also there exists integer k such that c = dk. Now since c = ax + by, we have
c = dk = (ma + nb)k = a(km) + b(nk).

Hence a solution for the equation ax + by = c is x_0 = km and y_0 = kn.
What is left to prove is that we have in?nitely many solutions. Let x = x_0 + (b/d)t and y = y_0 - (a/d)t. We have to prove now that x and y are solutions for all integers t. Notice that
ax + by = a(x_0 + (b/d)t) + b(y_0 - (a/d)t) = ax_0 + by_0 = c.
We now show that every solution for the equation ax + by = c is of the form
x = x_0 + (b/d)tand y = y_0 - (a/d)t.
Notice that since ax_0 + by_0 = c, we have a(x - x0) + b(y - y0) = 0.
Hence a(x - x0) = b(y - y0).
Dividing both sides by d, we get
a/d(x - x0) = b/d(y - y0).

Notice that (a/d, b/d) = 1 and thus we get by Lemma (a,b,c are positive integers such that (a, b) = 1 and a | bc, then a | c) that a/d | y - y0. As a result, there exists an integer t such that y = y0 - (a/d)t. Now substituting y - y0 in the equation a(x - x0) = b(y - y0). We get x = x0 + (b/d)t.

Example. The equation 3x+6y = 7 has no integer solution because (3, 6) = 3 does not divide 7.


Example. There are in?nitely many integer solutions for the equation 4x +6y = 8 because
 (4, 6) = 2 | 8. We use the Euclidean algorithm to determine m and n where 4m + 6n = 2. It turns out that 4(-1) + 6(1) = 2. And also 8 = 2.4. Thus x0 = 4.(-1) = -4 and y0 = 4.1 = 4 is a particular solution. The solutions are given by
 
x = -4 + 3t
 
y = 4 - 2t
for all integers t.

Least Common Multiple

We can use prime factorization to ?nd the smallest common multiple of two positive integers.

Definition 1. The least common multiple (l.c.m.) of two positive integers is the smallest positive integer that is a multiple of both. We denote the least common multiple of two positive integers a an b by [a, b] .

Example. [2, 8] = 8, [5, 8] = 40

We can figure out a, b once we have the prime factorization of a and b. To do that, let
$a = p_1^a_1 p_2^a_2 ...p_m^a_n$ and $b = p_1^b_1 p_2^b_2 ...p_m^b_n$ , where (as above) we exclude any prime with 0 power in both a and b. Then [a,b]=$p_1^[max(a1,b1)} p_2^{max(a2,b2)}... p_m^{max(an,bn)}$, where max(a, b) is the maximum of the two integers a and b. We now prove a theorem that relates the least common multiple of two positive integers to their greatest common divisor. In some books, this theorem is adopted as the de?nition of the least common multiple. To prove the theorem we present a lemma

Lemma 1. If a and b are two real numbers, then min(a, b) + max(a, b) = a + b

Proof. Assume without loss of generality that a >/== b. Then
max(a, b) = a and min(a, b) = b, and the result follows.

Theorem 1. Let a and b be two positive integers. Then
1. [a, b] >/= 0;
2. [a, b] = ab/(a, b); where (a,b) is GCD of a and b.

3. If a | m and b | m, then [a, b] | m

The infinitude of Primes

We now show that there are infinitely many primes. There are several ways to prove this result. An alternative proof to the one presented here is given as an exercise. The proof we will provide was presented by Euclid in his book the Elements.

Theorem 1. There are infinitely many primes.

Proof. We present the proof by contradiction. Suppose there are finitely many primes p1, p2, ..., pn, where n is a positive integer. Consider the integer Q such that Q = p1p2...pn + 1. By before Lemma 1, Q has at least a prime divisor, say q. If we prove that q is not one of the primes listed then we obtain a contradiction. Suppose now that q = pi for 1 </= i </= n. Thus q divides p1p2...pn and as a result q divides Q - p1p2...pn. Therefore q divides 1. But this is impossible since there is no prime that divides 1 and as a result q is not one of the primes listed. The following theorem discusses the large gaps between primes. It simply states that there are arbitrary large gaps in the series of primes and that the primes are spaced irregularly.

Theorem 2. Given any positive integer n, there exists n consecutive composite integers.

Proof. Consider the sequence of integers (n + 1)! + 2, (n + 1)! + 3, ..., (n + 1)! + n, (n + 1)! + n + 1

Notice that every integer in the above sequence is composite because k divides (n + 1)! + k if 2 </= k </= n + 1 by 4

The Sieve of Eratosthenes

Definition 1. A prime is an integer greater than 1 that is only divisible by 1 and itself.

Example. The integers 2, 3, 5, 7, 11 are prime integers. Note that any integer greater than 1 that is not prime is said to be a composite number. We now present the sieve of Eratosthenes. The Sieve of Eratosthenes is an ancient method of finding prime numbers up to a speci?ed integer. This method was invented by the ancient Greek mathematician Eratosthenes. There are several other methods used to determine whether a number is prime or composite. We first present a lemma that will be needed in the proof of several theorems.

Lemma 1. Every integer greater than one has a prime divisor.

Proof. We present the proof of this Lemma by contradiction. Suppose that there is an integer greater than one that has no prime divisors. Since the set of integers with elements greater than one with no prime divisors is nonempty, then by the well ordering principle there is a least positive integer n greater than one that has no prime divisors. Thus n is composite since n divides n. Hence n = ab with 1 < a < nand 1 < b < n. Notice that a < n and as a result since n is minimal, a must have a prime divisor which will also be a divisor of n.

Theorem 1. If n is a composite integer, then n has a prime factor not exceeding $\sqrt{n}$.

Proof. Since n is composite, then n = ab, where a and b are integers with 1 <a </= b < n. Suppose now that a > n, then $\sqrt{n}$<a </= b and as a result ab > $\sqrt{n}$$\sqrt{n}$=$\sqrt{n}$. Therefore a </= $\sqrt{n}$. Also, by Lemma 1, a must have a prime divisor a1 which is also a prime divisor of n and thus this divisor is less than a1 </=  a </=  n.


We now present the algorithm of the Sieve of Eratosthenes that is used to determine prime numbers up to a given integer.

  1. Write a list of numbers from 2 to the largest number n you want to test. Note that every composite integer less than n must have a prime factor less than $\sqrt{n}$. Hence you need to strike off the multiples of the primes that are less than $\sqrt{n}$
  2. Strike off all multiples of 2 greater than 2 from the list . The first remaining number in the list is a prime number.
  3. Strike off all multiples of this number from the list.
  4. Repeat the above steps until no more multiples are found of the prime integers that are less than $\sqrt{n}$

The Greatest Common Divisor

In this section we define the greatest common divisor (gcd) of two integers and discuss its properties. We also prove that the greatest common divisor of two integers is a linear combination of these integers. Two integers a and b, not both 0, can have only finitely many divisors, and thus can have only ?nitely many common divisors. In this section, we are interested in the greatest common divisor of a and b. Note that the divisors of a and that of |a| are the same.

Definition 1. The greatest common divisor of two integers a and b is the greatest integer that divides both a and b. We denote the greatest common divisor of two integers a and b by (a, b). We also define (0, 0) = 0.

Example. Note that the greatest common divisor of 24 and 18 is 6. In other words (24, 18) = 6.
There are couples of integers (e.g. 3 and 4, etc...) whose greatest common divisor is 1 so we call such integers relatively prime integers.

Definition 2. Two integers a and b are relatively prime if (a, b) = 1. Example. The greatest common divisor of 9 and 16 is 1, thus they are relatively prime. Note that every integer has positive and negative divisors. If a is a positive divisor of m, then ?a is also a divisor of m. Therefore by our definition of the greatest common divisor, we can see that (a, b) = (| a |, | b |). We now present a theorem about the greatest common divisor of two integers. The theorem states that if we divide two integers by their greatest common divisor, then the outcome is a couple of integers that are relatively prime.

Theorem 1. If (a, b) = d then (a/d, b/d) = 1.

Proof. We will show that a/d and b/d have no common positive divisors other than 1. Assume that k is a positive common divisor such that k | a/d and k | b/d. As a result, there are two positive integers m and n such that a/d = km and b/d = kn. Thus we get that a = kmd and b = knd. Hence kd is a common divisor of both a and b. Also, kd > or = d. However, d is the greatest common divisor of a and b. As a result, we get that k = 1.

The next theorem shows that the greatest common divisor of two integers does not change when we add a multiple of one of the two integers to the other.

Theorem 2. Let a, b and c be integers. Then (a, b) = (a + cb, b).

Proof. We will show that every divisor of a and b is also a divisor of a + cb and b and vise versa. Hence they have exactly the same divisors. So we get that the greatest common divisor of a and b will also be the greatest common divisor of a + cb and b. Let k be a common divisor of a and b. By Theorem 4, k | (a + cb) and hence k is a divisor of a + cb. Now assume that l is a common divisor of a + cb and b. Also by Theorem 4 we have , l | ((a + cb) - cb) = a. As a result, l is a common divisor of a and b and the result follows.

Example. Notice that (4, 14) = (4, 14 - 3 · 4) = (4, 2) = 2.
We now present a theorem which proves that the greatest common divisor of two integers can be written as a linear combination of the two integers.


Theorem 3. The greatest common divisor of two integers a and b, not both 0 is the least positive integer such that ma + nb = d for some integers m and n.



Proof. Assume without loss of generality that a and b are positive integers. Consider the set of all positive integer linear combinations of a and b. This set is non empty since a = 1 · a + 0 · b and b = 0 · a + 1 · b are both in this set. Thus this set has a least element d by the well-ordering principle. Thus d = ma + nb for some integers m and n. We have to prove that d divides both a and b and that it is the greatest divisor of a and b. By the division algorithm, we have 
a = dq + r,  0 < or = r < d.

Thus we have r = a - dq = a - q(ma + nb) = (1 - qm)a - qnb.

We then have that r is a linear combination of a and b. Since 0 < or = r < d and d is the least positive integer which is a linear combination of a and b, then r = 0 and a = dq. Hence d | a. Similarly d | b. Now notice that if there is a divisor c that divides both a and b. Then c divides any linear combination of a and b by a before Theorem . Hence c | d. This proves that any common divisor of a and b divides d. Hence c < or = d, and d is the greatest divisor. As a result, we conclude that if (a, b) = 1 then there exist integers m and n such that ma + nb = 1.


Defnition 3. Let a1, a2, ..., an be integers, not all 0. The greatest common divisor of these integers is the largest integer that divides all of the integers in the set. The greatest common divisor of a1, a2, ..., an is denoted by (a1, a2, ..., an).

Definition 4. The integers a1, a2, ..., an are said to be mutually relatively prime if (a1, a2, ..., an) = 1.
Example. The integers 3, 6, 7 are mutually relatively prime since (3, 6, 7) = 1 although (3, 6) = 3.

Definition 5. The integers a1, a2, ..., an are called pairwise prime if for each i = j,we have (ai, aj ) = 1.
Example. The integers 3, 14, 25 are pairwise relatively prime. Notice also that these integers are mutually relatively prime. Notice that if a1, a2, ..., an are pairwise relatively prime then they are mutually relatively prime.

Integer Divisibility

Definition 1. If a and b are integers such that a#0, then we say "a divides b" if there exists an integer k such that b = ka. If a divides b, we also say "a is a factor of b" or "b is a multiple of a" and we write a | b. If a doesn't divide b, we write a / b. For example 2 | 4.

Example:

a) Note that any even integer has the form 2k for some integer k, while any odd integer has the form 2k + 1 for some integer k. Thus 2|n if n is even, while 2 n if n is odd.
b) Every a in Z one has that a | 0.
c) If b in Z is such that |b| < a, and b # 0, then a / b.

Theorem 1. If a, b and c are integers such that a | b and b | c, then a | c.
Proof. Since a | b and b | c, then there exist integers k1 and k2 such that b = k1a and c = k2b. As a result, we have c = k1k2a and hence a | c.


Example. Since 6 | 18 and 18 | 36, then 6 | 36.



The following theorem states that if an integer divides two other integers then it divides any linear combination of these integers.


Theorem 2. If a, b, c, m and n are integers, and if c | a and c | b, then c | (ma + nb).



Proof. Since c | a and c | b, then by de?nition there exists k1 and k2 such that a = k1c and b = k2c. Thus ma + nb = mk1c + nk2c = c(mk1 + nk2), and hence c | (ma + nb).

The Principle of Mathematical Induction

We now present a valuable tool for proving results about integers. This tool is the principle of mathematical induction .

Theorem 1. The First Principle of Mathematical Induction

If a set of positive integers has the property that, if it contains the integer k, then it also contains k + 1, and if this set contains 1 then it must be the set of all positive integers. More generally, a property concerning the positive integers that is true for n = 1, and that is true for the integer n + 1 whenever it is true for the integer n, must be true for all positive integers. We use the well ordering principle to prove the first principle of mathematical induction.

Proof. Let S be the set of positive integers containing the integer 1, and the integer k + 1 whenever it contains k. Assume also that S is not the set of all positive integers. As a result, there are some integers that are not contained in S and thus those integers must have a least element x by the well ordering principle. Notice hat x = 1 since 1 in S. But x - 1 in S and thus using the property of S, x in S. Thus S must contain all positive integers.

Theorem 2. The Second Principle of Mathematical Induction


A set of positive integers that has the property that for every integer k, if it contains all the integers 1 through k then it contains k + 1 and if it contains 1 then it must be the set of all positive integers. More generally, a property concerning the positive integers that is true for n = 1, and that is true for all integers up to n + 1 whenever it is true for all integers up to n, must be true for all positive integers.


The second principle of induction is also known as the principle of strong induction. Also, the ?rst principle of induction is known as the principle of weak induction. To prove the second principle of induction, we use the first principle of induction.


Proof. Let T be a set of integers containing 1 and such that for every positive integer k, if it contains 1, 2, ..., k, then it contains k + 1. Let S be the set of all positive integers k such that all the positive integers less than or equal to k are in T . Then 1 is in S, and we also see that k + 1 is in S. Thus S must be the set of all positive integers. Thus T must be the set of all positive integers since S is a subset of T .

The Well Ordering and Pigeonhole Principle


The Well Ordering Principle
 

The Well Ordering Principle: A least element exist in any non empty set of positive integers.


This principle can be taken as an axiom on integers and it will be the key to proving many theorems. As a result, we see that any set of positive integers is well ordered while the set of all integers is not well ordered.
 


The Pigeonhole Principle
 

The Pigeonhole Principle: If s objects are placed in k boxes for s > k, then at least one box contains more than one object.

Proof. Suppose that none of the boxes contains more than one object. Then there are at most k objects. This leads to a contradiction with the fact that there are s objects for s > k.

Algebraic Operations With Integers

The set Z of all integers, which this book is all about, consists of all positive and negative integers as well as 0. Thus Z is the set given by Z = {..., -4, -3, -2, -1, 0, 1, 2, 3, 4, ...}. While the set of all positive integers, denoted by N, is defined by N = {1, 2, 3, 4, ...}. On Z, there are two basic binary operations, namely addition (denoted by +) and multiplication (denoted by ·), that satisfy some basic properties from which every other property for Z emerges.

1. The Commutativity property for addition and multiplication

a + b = b + a
a · b = b · a
2. Associativity property for addition and multiplication
(a + b) + c = a + (b + c)
(a · b) · c = a · (b · c)
3. The distributivity property of multiplication over addition
a · (b + c) = a · b + a · c.
In the set Z there are "identity elements" for the two operations + and ·, and these are the elements 0 and 1 respectively, that satisfy the basic properties
a +0 = 0+ a = a
a · 1=1 · a = a
for every a in Z.

The set Z allows additive inverses for its elements, in the sense that for every a in Z there exists another integer in Z, denoted by -a, such that 
a + (-a) = 0.

 While for multiplication, only the integer 1 has a multiplicative inverse in the sense that 1 is the only integer a such that there exists another integer, denoted by 1/a, (namely 1 itself in this case) such that

 a · 1/a = 1.

From the operations of addition and multiplication one can define two other operations on Z, namely subtraction (denoted by ?) and division (denoted by /). Subtraction is a binary operation on Z, i.e. defined for any two integers in Z, while division is not a binary operation and thus is de?ned only for some specific couple of integers in Z. Subtraction and division are de?ned as follows:

1. a - b is defined by a + (-b), i.e. a - b = a + (-b) for every a, b in Z

2. a/b is defined by the integer c if and only if a = b · c.

Kontak Kami

SMS/Phone : 082271051411
WhatsApp: 085246493737
Email: matematikakubisa@gmail.com

Statistik Pengunjung

Copyright © Matematika Ku Bisa. All rights reserved. Template by CB. Theme Framework: Responsive Design
Messenger Admin
×
_

Hai, Kamu bisa kirim pesan ke Admin di sini! Jangan lupa like halaman admin ya, terima kasih!