b is a Zero Divisor ( I think)

• Jul 23rd 2011, 03:25 PM
windoze
b is a Zero Divisor ( I think)
Im new and working on a proof - well actually i cant even start this proof.

If gcf (n,a) >1 prove there exists b not equal unto 0 mod n but a*b = 0 mod n.
Im even told that b = n/gcf(n,a)

any ideas or help will surely be appreciated and allow me to actually spend time with my family instead of staring at this problem for 4 hours getting nowhere.....

windoze
• Jul 23rd 2011, 09:03 PM
Anthonny
Re: b is a Zero Divisor ( I think)
I believe since they give you what b is you can simply substitute n/gcf(n,a) in for b and see if it fulfills those two conditions, which it does.
• Jul 23rd 2011, 09:05 PM
alexmahone
Re: b is a Zero Divisor ( I think)
Quote:

Originally Posted by windoze
Im new and working on a proof - well actually i cant even start this proof.

If gcf (n,a) >1 prove there exists b not equal unto 0 mod n but a*b = 0 mod n.
Im even told that b = n/gcf(n,a)

any ideas or help will surely be appreciated and allow me to actually spend time with my family instead of staring at this problem for 4 hours getting nowhere.....

windoze

Let gcd (n, a) = x > 1

Then, n = n1*x and a = a1*x

Clearly we can pick b = n1 because a*b = a1*x*n1 = a1*n = 0 (mod n)