1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Arithmetics problem

  1. Jan 5, 2013 #1
    Hi everyone
    I'm having difficulty in proving the following problem
    Give [itex]a\in \mathbb{Z}[/itex] and [itex]a \ne 0[/itex]. Prove that: there exist infinitely many composite numbers m such that [itex]a^{m-1}\equiv 1 mod m[/itex]
    I tried to find m number, which is satisfied with problem requirement, but I still haven't found it.
    Can you help me find m number?
    Thanks for your help!
     
    Last edited: Jan 5, 2013
  2. jcsd
  3. Jan 5, 2013 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    You are trying to prove there exist infinitely many and you cannot find even 1? You need to talk to your teacher about this!

    Suppose a= 3. Then you want to find prime m such that am-1= 1 (mod m).

    Okay, just try some prime numbers. If m= 5 then am-1= 34= 81= 1 (mod 5). Done!

    Perhaps I am misunderstanding your question.
     
  4. Jan 5, 2013 #3
    Thank you. But, in this problem, m is not prime number, m is composite number and a is an any integer.
     
    Last edited: Jan 5, 2013
  5. Jan 5, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    If m is odd then a=m-1 is a trivial solution. Other solutions are quite sparse. In the form a;m I found
    4;15, 4;85, 4;9, 15;85, 7;77, 8;21, 8;45, 8;63, 8;105, 8;65, 11;15, 11;45, 15;49, 16;51, 16;85, 16;91, 18;115, 19;105, 20;85, 21;69, 27;33, 31;33, 31;77, 32;93, 34;77, 35;99, 37;55, 38;115
     
  6. Jan 6, 2013 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Typo: should have been 4;91, not 4;9.
    Have now found a general solution for a even: set m = a2-1. Might be extensible to an infinite set of m values somehow.
     
  7. Jan 7, 2013 #6
    The m values are the Fermat pseudoprimes to base a. There are an infinity of them but they are generally not very dense; much less dense than primes.

    A proof is here: http://primes.utm.edu/notes/proofs/a_pseudoprimes.html - you aren't going to stumble on this by trial and error.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Arithmetics problem
Loading...