Friday, 6 July 2018

elementary number theory - Congruence proof using gcd concepts



Anyone can help me? The problem is:



We have that a \equiv b (\mod p), x|a, x|b, and x and p are relative primes, \gcd(x,p)=1. How to show that \dfrac{a}{x} \equiv\dfrac{b}{x} (\mod p)?



Thanks in advance.


Answer




Hint \ By Euclid's Lemma, \rm\, gcd(x,p)=1,\ \ x\mid \color{#c00}{a\!-\!b = pn}\:\Rightarrow\:x\mid n.\ Cancel \rm\,x\, from \rm\color{#c00}{a,b,n\ there}.


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

How to find \lim_{h\rightarrow 0}\frac{\sin(ha)}{h} without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...