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

Download Full-Text PDF Cite this Publication

Text Only Version

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

Leave a Reply

Your email address will not be published. Required fields are marked *