A stupid question - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Computation - 科学计算

A stupid question

A stupid question# Computation - 科学计算

r*e2004-07-27 07:07

1 楼

I met a problem which is easy intuitively, but I don't know how to prove it.
Please help me on this.
For all positive integer n, a, and b, if n|ab, gcd(a, n) = 1, then n|b.
gcd is greatest common divisor, n|ab means n divides a*b.
Thanks

B*n2004-07-27 07:07

2 楼

if (a,n)=1 then there exists integers x and y such that ax+ny=1
n|ab=>n|axb=>n|(1-ny)b=>n|b

【在 r****e 的大作中提到】

: I met a problem which is easy intuitively, but I don't know how to prove it.
: Please help me on this.
: For all positive integer n, a, and b, if n|ab, gcd(a, n) = 1, then n|b.
: gcd is greatest common divisor, n|ab means n divides a*b.
: Thanks