Beyond the Limits of Fermat’s and Euler’s Theorems

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, Co-prime, residue.

1. 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.

2. 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 co-prime (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 co-prime to 35 , etc. The integer 1 is co-prime to every integer in .

   Remark 2.1: If m is a prime number, then every non-zero 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:

   1. a b mod n

      (reflexive)

   2. If a b mod n , then b a mod n

   3. If a b mod n and b c mod n

      (symmetric)

      then a c mod n (transitive)

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

3. 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)

4. 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.

5. REFERENCES

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

2. Eugen Vedral, Solutions of Some Classes of Congruences, The Teaching of Mathematiccs, Vol. IX, 2006, 41-44.

3. 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

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

5. Journal of Number Theory, Vol 188, 2018; 324-334

6. S. R. Joshi, Nonlinear Congruences in the Theory of Numbers, Bulletin of the Marathwada Mathematical Society, Vol. 12, 2011, 24-31.

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