Results 1 to 4 of 4

Math Help - Congruence/Residue Class

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    21

    Congruence/Residue Class

    Q:
    Let f(n) = a_0x^n + ... + a_n be a polynomial over Z
    Show that if r consecutive vales of f (i.e. values for consecutive integers) are all divisible by r, then r|f(m) for all m \in Z
    Follow Math Help Forum on Facebook and Google+

  2. #2
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    the remainder of the r consecutive integer must be 0,1,...,r-1.
    since f(x)\mod r=f(x\mod r), f(0)\mod r=f(1)\mod r=...=f(r-1)\mod r=0, \forall m,f(m)\mod r=f(m\mod r)=0since m \mod r\in\{0,1,...,r-1\}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2009
    Posts
    21
    Cool, thx for the response

    A few questions:
    1. I believe I came up with something similar to the proof you gave but I was wondering if it is required to prove that m mod r \in {0, 1, ... ,r-1} or is it obvious?

    What I am thinking is that that since we are working with mod r and all numbers should be represented by another number mod r then it is safe to assume m mod r \in {0, 1, ... ,r-1}. Is that correct?

    2. In order for this to be true, what does r have to equal? A second part to this question says that this is true with r > 1 and (a_0, ... , a_n) = 1. The problem I see with this is the a_n component of the function
    Follow Math Help Forum on Facebook and Google+

  4. #4
    ynj
    ynj is offline
    Senior Member
    Joined
    Jul 2009
    Posts
    254
    Quote Originally Posted by dlbsd View Post
    Cool, thx for the response

    A few questions:
    1. I believe I came up with something similar to the proof you gave but I was wondering if it is required to prove that m mod r \in {0, 1, ... ,r-1} or is it obvious?

    What I am thinking is that that since we are working with mod r and all numbers should be represented by another number mod r then it is safe to assume m mod r \in {0, 1, ... ,r-1}. Is that correct?

    2. In order for this to be true, what does r have to equal? A second part to this question says that this is true with r > 1 and (a_0, ... , a_n) = 1. The problem I see with this is the a_n component of the function
    let p=x\mod r, then p=\min\{y|y\geq 0,x=y+kr,k\in Z\},then obviously, p<r
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Rewording of a congruence class problem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 14th 2010, 04:50 AM
  2. Replies: 6
    Last Post: December 5th 2009, 06:53 AM
  3. one more quadratic residue congruence problem please
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 20th 2009, 09:27 AM
  4. congruence relation / residue classes
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 9th 2009, 02:42 PM
  5. Solutions in a congruence class
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 31st 2009, 04:51 PM

Search Tags


/mathhelpforum @mathhelpforum