def is_coprime(a, b):
    """Hàm ktra a và b có phải là nguyên tố cùng nhau"""
    while b:
        a, b = b, a % b
    return a == 1

n = int(input("Nhập stn n: "))
count = 0

for i in range(1, n+1):
    if is_coprime(i, n):
        count += 1

print(f"Số lượng số nguyên tố cùng nhau với n là {count}.")

làm ơi cíuuuu

Tham Khảo:

#include <bits/stdc++.h>

using namespace std;

long long n,m,x,i;

//chuongtrinhcon

long long ucln(long long a,long long b)

{

if (b==0) return(a);

else return(ucln(b,a%b));

}

//chuongtrinhchinh

int main()

{

cin>>m>>n;

x=ucln(m,n);

for (i=1; i<=x; i++) if (x%i==0) cout<<i<<" ";

cout<<endl;

cout<<"Uoc chung lon nhat="<<x<<endl;

cout<<"Boi chung nho nhat="<<(m*n)/x<<endl;

return 0;

}

Vì 396 : a dư 30 nên a > 30

Theo bài ra ta có : 

396 chia a dư 30 

=> ( 396 - 30 ) \(⋮\)a => 366  \(⋮\)a

Lại có : 473 chia a dư 23

=> ( 473 - 23 ) \(⋮\)a => 450 \(⋮\)a

Từ (1) và (2) => a \(\in\)ƯC( 366;450)

Ta có : 366 = 2 .3 . 61

             450 = 2 . 3² . 5²

Khi đó ƯCLN( 366;450 ) = 2 . 3 = 6

=> ƯC( 366;450 ) = Ư(6) = { 1 ;2 ; 3 ; 6 }

Vậy a \(\in\){1;2;3;6}

Gọi ƯCLN(A; B) = d

=> A ; B chia hết cho d

=> m + n chia hết cho d  và B = m² + n² chia hết cho d 

m + n chia hết cho d => m(m+ n) chia hết cho d => m² + mn chia hết cho d

=> (m² + mn) - (m² + n²) chia hết cho d => n(m - n) chia hết cho d

Nhận xét: n và m - n nguyên tố cùng nhau vì 

Gọi ƯCLN(n;m - n) = d' => n ; m - n chia hết cho d' => n; m chia hết cho d' => d' là ước chung của m; n

Mà theo bài cho ƯCLN(m; n) = 1 nên d' = 1

Vậy n; m - n nguyên tố cùng nhau 

Ta có n(m - n) chia hết cho d => n chia hết cho d hoặc m - n chia hết cho d

+) Trường hợp:  n chia hết cho d : Ta có m + n chia hết cho d nên m chia hết cho d => d là ước chung của m ; n mà ƯCLN(m; n) = 1

=> d = 1 

+) Trường hợp:  m - n chia hết cho d: Ta có m + n chia hết cho d => (m - n) + (m + n) chia hết cho d => 2m chia hết cho d

- Khi m lẻ  => 2 chia hết cho d hoặc m chia hết cho d

Nếu 2 chia hết cho d mà d lớn nhất => d = 2

Nếu m chia hết cho d , theo trường hợp trên => n chia hết cho d => d = 1

- Khi m chẵn, vì m; n nguyên tố cùng nhau nên n lẻ . Lại có 2n chia hết cho d => 2 chia hết cho d hoặc n chia hết cho d

Quay lại trường hợp như trên => d = 2 hoặc 1

Vậy d = 1 hoặc d = 2

Gọi ƯCLN(A; B) = d

=> A ; B chia hết cho d

=> m + n chia hết cho d  và B = m² + n² chia hết cho d 

m + n chia hết cho d => m(m+ n) chia hết cho d => m² + mn chia hết cho d

=> (m² + mn) - (m² + n²) chia hết cho d => n(m - n) chia hết cho d

Nhận xét: n và m - n nguyên tố cùng nhau vì 

Gọi ƯCLN(n;m - n) = d' => n ; m - n chia hết cho d' => n; m chia hết cho d' => d' là ước chung của m; n

Mà theo bài cho ƯCLN(m; n) = 1 nên d' = 1

Vậy n; m - n nguyên tố cùng nhau 

Ta có n(m - n) chia hết cho d => n chia hết cho d hoặc m - n chia hết cho d

+) Trường hợp:  n chia hết cho d : Ta có m + n chia hết cho d nên m chia hết cho d => d là ước chung của m ; n mà ƯCLN(m; n) = 1

=> d = 1 

+) Trường hợp:  m - n chia hết cho d: Ta có m + n chia hết cho d => (m - n) + (m + n) chia hết cho d => 2m chia hết cho d

- Khi m lẻ  => 2 chia hết cho d hoặc m chia hết cho d

Nếu 2 chia hết cho d mà d lớn nhất => d = 2

Nếu m chia hết cho d , theo trường hợp trên => n chia hết cho d => d = 1

- Khi m chẵn, vì m; n nguyên tố cùng nhau nên n lẻ . Lại có 2n chia hết cho d => 2 chia hết cho d hoặc n chia hết cho d

Quay lại trường hợp như trên => d = 2 hoặc 1

Vậy d = 1 hoặc d = 2

Gọi UCLN(A,B)=d

Ta có:\(\hept{\begin{cases}A⋮d\\B⋮d\end{cases}}\)\(\Rightarrow\hept{\begin{cases}m+n⋮d\\m.m+n.n⋮d\end{cases}}\)\(\Rightarrow\hept{\begin{cases}\left(m+n\right)\left(m-n\right)⋮d\\m.m+n.n⋮d\end{cases}}\)

\(\Rightarrow\hept{\begin{cases}m.m-n.n⋮d\\m.m+n.n⋮d\end{cases}}\)\(\Rightarrow\left(m.m-n.n\right)+\left(m.m+n.n\right)⋮d\)

\(\Rightarrow2.m.m⋮d\Rightarrow m.m⋮d\Rightarrow m⋮d\) vì UCLN(m,d)=1

\(\Rightarrow n⋮d\)

\(\Rightarrow d\inƯ\left(m,n\right)=1\)

Vậy UCLN((A,B)=1