 Open Access
 Authors : Zuonaki Ongodiebi , Tom Otobong , Udeme O. Ini
 Paper ID : IJERTV9IS030157
 Volume & Issue : Volume 09, Issue 03 (March 2020)
 Published (First Online): 16032020
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Beyond the Limits of Fermat’s and Euler’s Theorems
Zuonaki Ongodiebi1 and Tom Otobong2 and 3 Udeme O. Ini
1, 3Department of Mathematics and Computer Science, Niger Delta University Amassoma, Bayelsa State
2Department of Mathematics, Michael Okpara University of Agriculture, Umudike, Abia State
Abstract: We have shown that beyond the limits of Fermats and Eulers theorems, there is a ray of hope to ascertain the remainder when a number n divides a huge number a . Few illustrative examples are solved and a new relevant proposition is given.
Key words: Modulo, Congruence, Coprime, residue.

INTRODUCTION
Fermats and Eulers theorems are useful in finding solutions to linear and nonlinear congruences Eugen (2006) and Joshi (2011). See Adel (2018) and Vishnu (2018) for further details; since they provide easy methods to determine the remainder when a number n divides another number say a if certain conditions or restrictions are met . These restrictions are stated in
theorems 3.1 and 3.2. Recently, Brierly et.al (2019) and Saimir (2018) have provided proofs of Fermats last theorem as well as Fermats conjecture in the domain of natural numbers. The condition when the given problem do not satisfy the conditions of Fermats and Eulers theorems have never been reported in literature; thereby, motivating this research. Here, we have provided solutions to problems that do not satisfy the conditions of Fermats and Eulers theorems.

PRELININARIES
For a given integer m in ; let m denotes the set 0,1, 2, , m 1 . The set m is also known as the set of all remainders (or residues) modulo m .
2.1 Let m and n be integers, where m is positive. Then by remainders theorem, we can write
n qm r
1
where 0 r m and q is an integer. Equation (1) can be interpreted in the language of congruence which means that n is congruent to r modulo m for some integer q ; denoted by n r mod m .
Definition 2.1: If m is a positive integer and a, b are in , then we say that a is
congruence to b modulo m (written as a b mod m), if a b is divisible by m .
Definition 2.2: An integer a is said to be coprime (or relatively prime) to another
integer b if the greatest common divisor (g.c.d) of a and b is 1 that is gcd(a,b) 1
For example 8 is coprime to 35 , etc. The integer 1 is coprime to every integer in .
Remark 2.1: If m is a prime number, then every nonzero element of m is co prime to m .
Definition 2.3: Let n is a positive integer and n as defined above. Let
x,n n x : x, n 1, x n. Then the cardinal number of x,n n is
denoted by n . The function is called Eulers phi function.
For example 8 4, 7 6, etc. In general, for any prime p , p p 1
Properties of Congruence
For any integers a and b and a positive integer n , we have the following:

a b mod n
(reflexive)

If a b mod n , then b a mod n

If a b mod n and b c mod n
(symmetric)
then a c mod n (transitive)

If a b mod n and c d mod n , then a c b d mod n also, ac bd mod n


ILLUSTRATIVE EXAMPLES: We know that 23 2mod 7 . By squaring this, we have
232 4 mod 7 and also 233 8 mod 7 1mod 7 by transitive property stated above. With that above process, it becomes easy to find remainders of huge numbers.
Example 1: Find the remainder when 19139
Solution: Note that 19 9mod10
is divided by 10 .
192 81mod10 1mod10
now (192 )69 19138 1mod10 . Therefore,
19138 19 1 9 mod10
that is19139 9 mod10 the remainder is 9. Pretty simple!
Example 2: Determine the remainder when 22738 is divided by 17 .
Solution: 22 5mod17
222 25 mod17 8 mod17
223 125 mod17 6 mod17
224 625 mod17 13mod17
Proceeding in this form will lead us to frustration, and as a result, we present the following theorem.
Theorem 3. 1 (Fermats Theorem)
If a Z and p is a prime not dividing a , then p divides ap1 1. That is ap1 1mod p for a not 0 mod p .
Applying Fermats theorem to example 2, we have that a 22 and
ap1 1mod17 2216 1mod17
(2216 )46 22736 1mod17 and
222 8 mod17
22738 8mod17
Therefore, the remainder is 8.
p 17 . Thus
Suppose in example 2 above, the modulus was 15 ; that is 22738 mod15 then Fermats theorem fails to provide solution since
15 is not a prime number. To handle such problems, consider the following theorem.
Theorem 3.2 (Eulers Theorem)
If a is an integer relatively prime to n , then a (n) 1 is divisible by n . That is
a (n) 1mod n
Example 3: Use Eulers theorem to find the remainder when 22738 is divided by 15 .
Solution: Since the gcd(22,15) 1 , Euler's theorem is applicable. Now a 22 , n 15 and
228 1mod15
(228 )92 22736 1mod15 and
22 7 mod15
222 49 mod15 4 mod15
22738 4mod15 leaving a remainder 4
(n) 8 . It follows that
Example 3: Determine the remainder when 354 is divided by 66 . In this example, 66 is not a prime number which implies
that Fermats theorem can not be applied. Also the gcd(3, 66) 3
prime and as a result, Eulers theorem cannot be applied! What next?
which obviously means 3 and 66 are not relatively
To solve the above problem, let us first consider a simple version of the given problem: Find the remainder when 34 is divided by 66 i.e 34 mod 66 .
Clearly
3 gives
34 81 15 mod 66 ; thus the remainder is 15. Alternatively, a 3 and n 66 . By division of
34 mod 66 by
33 mod 22 33 27 5 mod 22
Now multiply through the congruence (3.1) by
a 3;
(3.1)
i.e 3 33 3 5 mod 3 22 or 34 15 mod 66 which also results to the same remainder. With this ray of hope, let us solve example 3.
The given problem is
354 mod 66 . By dividing through by 3 , we have
353 mod 22 . At the point, we can now apply Eulers theorem since 3 and 22 are relatively prime. Thus
3 (22) 310 1mod 22
350 1mod 22
33 5 mod 22
353 5 mod 22
354 15mod 66 . Thus the remainder is 15 .
Remarks: It is a mere coincidence that 34 mod 66 and 354 mod 66 have the same
remainder. The example we considered, observe that n a .
Example 4: Find the remainder when 2541 is divided by 15.
Solution: Again, 15 is not a prime number and as such, Fermats theorem can not be applied. Also, the
gcd(25,15) 1 which violates Eulers theorem. The given problem is
2541 mod15
Divide through by 5
581 mod 3
Now since the gcd(3, 5) 1and also 3 is prime, we can apply either Fermats or Eulers theorems. By applying Fermats theorem, we have
580 1mod 3 and since 5 2mod3 ; we have
581 2 mod 3
at this point, we multiply through by 5
582 10 mod15 or
2541 10 mod15 . Thus the remainder is 10 .
Remark: Observe that in this example, n a . Thus we state the following proposition.
Proposition 3.1
Suppose a and n are integers and n in not a prime; and suppose also that gcd(a, n) 1 , then the remainder when am is divided by n is given by
a{am1 mod(n / a)} if n a
r am
gcd(a, n){
mod(
n )} if n a
gcd(a, n) gcd(a, n)

CONCLUSION
Wehave shown that the remainder when a number n divides another number say a can be easily determined even if it does not satisfy the criteria for both Fermats and Eulers theorems. We demonstrate our claim with relevant examples.

REFERENCES

Adel, Betina and Emmanuel, Lecouturier, Congruence formulas for Legendre modular polynomials. Journal of Number Theory, Vol 188, 2018 7187

Eugen Vedral, Solutions of Some Classes of Congruences, The Teaching of Mathematiccs, Vol. IX, 2006, 4144.

J. E. Briervely, Takashin, Ito and Hidegoro Nakano, A simply proof of Fermats last theorem. Scholar Journal of Applied Sciences and Research,
Vol. 2, 2019; 1 4

K. Vishinu Namboothin, On the number of solutions of a restricted linear congruence

Journal of Number Theory, Vol 188, 2018; 324334

S. R. Joshi, Nonlinear Congruences in the Theory of Numbers, Bulletin of the Marathwada Mathematical Society, Vol. 12, 2011, 2431.

Saimir, A. Lolja, The proof of the Fermats conjecture in the correct domain. Vol. 35, 2018; 53 74