Fermat’s Little Theorem and the Primitive Roots and Quadratic Residues

Number Theory
Student’s Name
Course Title
Institutional Affiliations
Fermat’s little theory
1 Question 1
* State and prove Fermat’s little theoremThe theory states that with P as a prime number, any integer raised to this power minus the integer is a multiple of P (Fostvedt, 2020). In other words, ∝p≡ ∝(mod p)
Proof:
the numbers 0,1,2….p-1are in the list of possible remainders when you divide an integer by p.multiplying the numbers by ∝we are going to obtain 0, ∝,2∝, 3∝,4∝…..p-1∝If we are to deduct P from the numbers as suggested in the theory, the list is rearranged.leaving out the zero, and multiplying the numbers in each of the lists the final result is congruent modulo p∝*2∝*3∝*…..*p-1∝≡1*2*3*4*…..*p-1mod pPutting together the like terms we obtain∝p-1p-1! ≡p-1!mod p
Here we realize that both the left hand side and the right hand side contain the
term p-1!
and thus we didide both sides by this termWe obtain ∝p-1≡1mod por ∝p≡∝mod pand thus the proof.
B. State and prove/disapprove the contrapositive of Fermat’s little theoremthe contrapositive of Fermat’s little theorem provides that if the product of a and p fails to be congruent to a modulo p, then one does not consider p as a prime (Dougherty, 2020). The contrapositive may be used to prove that not all numbers p are prime numbers.
proof:
suppose we have been tasked with showing that 341 is not a prime number using the fermat'slittle
theorem. We first of of all need to note that 73=343This is equivalent to 2mod 341
and210=1024=1mod 3417341=73-113+2
≡211372=2110.23.72
≡8.49=
392≡51mod 341We are therefore comfortable concluding that 341 is not a prime number.
C. Explain, in plain terms, what Fermat’s little theorem means and how important it is in mathematics.
The theorem states that if p is a given number that can only be divided by one and itself, therefore, any integer raised to this power minus the integer is a multiple of P. In other words, ∝p≡ ∝(mod p)
for example if a=2 and p=7 then raising 2 to power 7 gives 128
subtracting 2 from 128=126 which is a multiple of 7 by 18
Now let us explore some of the practical uses of Fermat’s theory in practical mathematics.
let n>2 be a positive integer and let b≥2 be number that is indivisible by nbn-1mod n=1, then it follows that n is a prime number. The theory holds for most positive integers b but few excemptions are madeMathematics have a theory that says all positive integers b obey the rule given.this is the fastest ways to compute a modular exponentiation involving converse.
This enables us to compute even larger primes in a fraction of a second.The uses include cryptography with the RSA emcryption techniques (Raghunandan,
Aithal, & Shetty,2019)This theorem is also used in the Eulers theorem and is a basic
concept in the number theorem.
2. Primitive roots and quadratic residues
A. in plain language, answer the following
i. what is a complete residue system
A given residue of a modulo m indicates that integers congrue...