# Tagged Questions

73 views

61 views

### Matrix restoring (modulo n)

Let $m,n\geqslant 2$, and $A\in \mathcal{M}_n(\mathbb Z)$ such that $\det A \equiv 1 \pmod m$. Does it (necessarily) exist $M\in \mathrm{GL}_n(\mathbb Z)$ such that $A\equiv M \pmod m$?
278 views

### The largest integer less than $n$ is $n-1$

Let $n$ be a positive integer. Prove that the largest integer which is less than $n$ is $n-1$. Attempt of a solution: Since $n$ is a positive integer $n>0$. I think I have to use the well-ordering ...
29 views

### $p$ and $q$ are primes. Prove $\forall n,k\in \mathbb N, (p^n\mid q^k⇒p=q)$ [duplicate]

I'm having trouble answering this question, can anyone help explain a full solution of this problem? I will be very grateful. Thanks!
21 views

### Let n and k be positive integers. If n ≥ (k + 1), then n! + (k + 1) is a composite number

I've been having trouble with finding the proof for this question. Can anybody explain the solution to me? Thanks so much!
42 views

### GCD question involving coprimes

How can I prove that if $\gcd(a, b) = 1$, then $\gcd(ab, c) = \gcd(a, c) \times \gcd(b, c)$? By eea there exists $ax+by=1$ from $\gcd(a,b)=1$ so a and be are co-primes there also exists $dk=a$ and ...
17 views

### Proving $k$ is a common divisor of $a$ and $b$ iff $k\,|\gcd(a,b)$ — converse

I'm currently trying to solve the converse of this statement is true after proving the normal version is true. If $k$ is a common divisor of $a$ and $b$, then $k \,| \gcd(a, b)$ So far I know the ...
24 views

### Questions relating to gcd

Assume a, b and c are positive integers. 1) Suppose that a | b. Show that gcd(a, c) ≤ gcd(b, c). 2) Suppose that a ≤ b. Is it necessarily true that gcd(a, c) ≤ gcd(b, c)? I'm having trouble with ...
20 views

Suppose $n_1$, $n_2$, $\dots$ $n_k$ are given natural numbers. Can we write the addition $\sum$ of these $k$ numbers in terms two other functions $f$ and $g$? i.e. $\sum(n_1, n_2,\dots,n_k)=f(n_1, ... 2answers 158 views ### Number theory problem.Primes modules. If $$a^p\equiv b^p \pmod p$$ where$p$is prime prove that $$a^p\equiv b^p \pmod{p^2}$$ that problem was at my exam today on number theory and i just didnt have a clear mind to solve it.Although i ... 4answers 60 views ### Number theory!Polynomial modules From Fermats theorem we know that for every$a \in \mathbb{Z}$, $$a^p\equiv a \mod{p}$$. But the polynomial$x^p$it is not equal to the polynomial$x$( as a Congruence ). Why?Also when you want to ... 1answer 41 views ### Polynomial Diophantine Equations So in general how does one decide if: $$a_0 + a_1x + a_2x^2 ... a_{n_1}x^{n_1} = b_1y + b_2y^2 ... + b_{n_2}y^{n_k}$$ Has solutions for integers$x,y$given real numbers$a_0, a_1. .. a_{n_1}, b_1 , ...
76 views

Let $N=pq$ where $p$ and $q$ are primes of the form $4k+1$. Let $\mathbb{Z}_N$ be the set of integers modulo $N$ and $\mathbb{Z}_N^*$ be the units in $\mathbb{Z}_N$. Let $QR$ be the quadratic ...
40 views

### Show that the number 9 divides the number $m$ if and only if the sum of the digits of the number $m$ is divisible by 9.

Show that the number 9 divides the number $m$ if and only if the sum of the digits of the number $m$ is divisible by 9. Show that the number 3 divides the number $m$ if and only if the sum of the ...
106 views

### Is there any usage of this sum formula?

Let $\phi$ be the Euler phi function, then $$n=\sum_{d|n}\phi(d)$$ It is one of the most famous formulas in number theory. It can be generalized by using groups. Let $G$ be a group of order $n$ and ...
35 views

### What are the terms for the elements in the Euclidean algorithm $a = qb + r$?

In a ring $R$ with a Euclidean norm $N$, given $a,b \in R$ with $b\neq 0$, there are elements $q, r$ such that $a = qb + r$. Is there any special terminology for the elements $a,b,q,r$ in this ...
21 views

### Does $a^{\phi(p^k)/2} \equiv -1 \pmod {p^k}$ imply $a$ is a primitive root modulo $p$, where $p$ is an odd prime and $k$ an integer $\ge 2$?

Suppose $a$ is a primitive root $\pmod p$. Does $$a^{\phi(p^k)/2} \equiv -1 \pmod {p^k}$$ imply $a$ is a primitive root modulo $p^k$, where $p$ is an odd prime and $k$ an integer $\ge 2$ ? I've been ...
41 views

### Prove $n>1$ is prime $\iff \alpha^{n-1} = 1 \ \forall \alpha \in \mathbb Z_n\setminus\{[0]\}$.

Prove $n>1$ is prime $\iff \alpha^{n-1} = 1 \ \forall \alpha \in \mathbb Z_n\setminus \{[0]\}$. I have proven $\Rightarrow$ which is an immediate consequence of Euler's theorem, however I ...
50 views

### Proof of Pocklingtons theorem: why do we have $\text{ord}_n(a) \mid (q-1)$ but $\text{ord}_n(a) \nmid (n-1)/p_i$?

Proof of Pocklingtons theorem: why do we have $\text{ord}_n(a) \mid (q-1)$ but $\text{ord}_n(a) \nmid (n-1)/p_i$ ? And why does $p_i^{\alpha_i} \mid \text{ord}_n(a)$ ? I see that ...
### Proof of k'th power theorem: $x^k \equiv a \pmod n$ has a solution $\iff$ $a^{\phi(n)/\gcd(k, \phi(n))} \equiv 1 \pmod n$.
Proof of k'th power theorem: $x^k \equiv a \pmod n$ has a solution $\iff$ $a^{\phi(n)/\gcd(k, \phi(n))} \equiv 1 \pmod n$, where $n$ has a primitive root. I have proven the following theorem ...