Results 1 to 3 of 3

Thread: Wondering if a difference of 1 in a relation affects my proof

  1. #1
    Junior Member
    Joined
    Jan 2009
    Posts
    27

    Wondering if a difference of 1 in a relation affects my proof

    Let $\displaystyle k,n$ be integers such that $\displaystyle 1 <= k <= n <= p-1$ where $\displaystyle p is prime$.
    Assume $\displaystyle (a,p) = 1$.
    Show that $\displaystyle ak \equiv an mod p$ iff$\displaystyle k = n$.

    Proof:
    $\displaystyle ak \equiv an mod p$
    $\displaystyle k \equiv n mod p$ (since $\displaystyle (a,p) = 1$)

    Then I used a Lemma that states:
    Let$\displaystyle i $and $\displaystyle j$ be integers with $\displaystyle 1 <= i <= j <= m$. If $\displaystyle i \equiv j mod m$, then $\displaystyle i = j$.

    Where I use $\displaystyle i = k$, $\displaystyle j = n$, and $\displaystyle m = p$. So that gives $\displaystyle k = n$. My question is, am I allowed to use the theorem if the equivalences are 1 off?:
    $\displaystyle 1 <= k <= n <= p-1$ Proof
    $\displaystyle 1 <= i <= j <= m$ Lemma

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by Th3sandm4n View Post
    Proof:
    $\displaystyle ak \equiv an mod p$
    $\displaystyle k \equiv n mod p$ (since $\displaystyle (a,p) = 1$)
    Once you know $\displaystyle k\equiv n(\bmod p)$ it would follow that $\displaystyle k=n$. This is because $\displaystyle k\leq n$ and so $\displaystyle 0\geq 0 n-k<p$. The only way for $\displaystyle n-k$ to be divisible by $\displaystyle p$ is for $\displaystyle n-k = 0\implies n=k$.

    This is Mine 12,3th Post!!!
    Last edited by ThePerfectHacker; Mar 29th 2009 at 08:57 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2009
    Posts
    27
    yeah I started my proof trying to get it to show$\displaystyle n-k = 0$ but then saw the Lemma and thought that would show it better. Thank you for the clearer explanation though, and congrats on the posts, that is a lot of helping!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Apr 23rd 2011, 10:38 AM
  2. [SOLVED] Difference equation - recurrence relation
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: Aug 2nd 2010, 09:08 AM
  3. Replies: 0
    Last Post: Oct 18th 2009, 11:21 AM
  4. Relation proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 16th 2009, 09:14 AM
  5. equivalence relation proof
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: Jul 3rd 2006, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum