-2
votes
1answer
44 views

Suppose $x ≡ 1 \ (\text{mod}\ 8)$, and $x ≡ 9\ (\text{mod}\ 12)$ has a solution $x = x_0$. How many solutions modulo 24? [on hold]

Suppose $x ≡ 1\ (\text{mod}\ 8)$, and $x ≡ 9\ (\text{mod}\ 12)$ has a solution $x = x_0$. How many solutions modulo $24$ are there to this system of congruences?
-3
votes
0answers
27 views

For m, n ≥ 2, let f : Z → Z/mZ×Z/nZ be the ring homomorphism defined by f(a) = (a + mZ, a + nZ)… read below. [on hold]

For m, n ≥ 2, let f : Z → Z/mZ×Z/nZ be the ring homomorphism defined by f(a) = (a + mZ, a + nZ). (i) The kernel K of f is the ideal qZ for some number q (depending, of course, on m and n). Describe q. ...
6
votes
1answer
59 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$?
7
votes
4answers
272 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 ...
-1
votes
1answer
28 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!
0
votes
3answers
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!
1
vote
2answers
32 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 ...
0
votes
1answer
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 ...
2
votes
1answer
17 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 ...
0
votes
1answer
20 views

Sum of k natural numbers in terms of two other functions

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, ...
3
votes
2answers
152 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 ...
1
vote
4answers
59 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 ...
0
votes
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 , ...
1
vote
1answer
71 views

quadratic residue difference set

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 ...
0
votes
1answer
38 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 ...
3
votes
2answers
96 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 ...
1
vote
1answer
30 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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
49 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 ...
1
vote
3answers
104 views

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 ...
2
votes
2answers
60 views

Why does it follows that $\alpha \in (\mathbb Z_p^*)^2 \iff \alpha^{(p-1)/2} = 1$ from proved results?

Suppose I 've proved the following, where $(\mathbb Z_p^*)^2$ denotes the set of unit residue classes modulo $p$. Why does it then follows that $\alpha \in (\mathbb Z_p^*)^2 \iff \alpha^{(p-1)/2} = ...
1
vote
1answer
69 views

Exercise in algebra with modulo

I'm studying Cassels' book Elliptic Curves for a week now, and I'm at the local global principle. I'm trying to prove the first exercise of this chapter, which says Let $p > 2$ be prime and ...
0
votes
0answers
22 views

Why does this theorem provide a neccesary and sufficient condition for a $2 \times 2$ linear system of congruences to have a unique solution?

Why does the following theorem both provide a neccesary and sufficient condition for a $2 \times 2$ linear system of congruences to have a unique solution ? I see that $\gcd((ad-bc),m) = 1$ is a ...
3
votes
0answers
48 views

Is $\mathbb{Z}_9^*$ cyclic?

I'm reading "A course in algebra" (2003) by E. B. Vinberg to have a basic understanding on algebra. Now I got a question. Exercise 4.46. says "Prove that the group $\mathbb{Z}_n^*$ of invertible ...
0
votes
0answers
15 views

$m^2 = \prod_{i=1}^k p_i^{2e_i} \equiv 1 + \sum_{i=1}^k e_i (p_i^2-1) (\mod 64)$ imply $(m^2 - 1)/8 \equiv \sum_{i=1}^k e_i (p_i^2-1)/8 (\mod 2)$?

Let $m$ be an odd positive integer with canonical decomposition $\prod_{i=1}^k p_i^{e_i}$. I know $$m^2 = \prod_{i=1}^k p_i^{2e_i} \equiv \prod_{i=1}^k [1+e_i(p_i^2-1) \equiv 1 + \sum_{i=1}^k e_i ...
1
vote
1answer
35 views

What can we say about this quantity?

Let $\phi(n)$ be the Euler phi-function. If $a>1$ is an integer, then what is the remainder when $\phi(a^n - 1)$ is divided by $n$ in accordance with the Euclidean algorithm?
1
vote
1answer
10 views

Gauss' Lemma: $r_1, \ldots, r_k, p - s_1, \ldots, p-s_{\nu}$ are all incongruent where $r_i, s_j$ are least residues.

I'm having trouble understanding a step in the below proof of Gauss' Lemma. I see that $r_1, \ldots, r_k, p - s_1, \ldots, p-s_{\nu}$ are all less than $p/2$ and it follows that $r_1,\ldots, r_k$ ...
0
votes
0answers
33 views

The elegant expression in terms of gcd and lcm - algebra - (2)

Definition: suppose a quantity $P$ is identified by $$ \frac{P}{k}\simeq \frac{P}{k}+1 $$ what we mean is that $$ P= 0\pmod{k}. $$ That means that when $P \to P+k$, then $$ \frac{P}{k}\to ...
2
votes
1answer
39 views

The elegant expression in terms of gcd and lcm - algebra

Given three positive integer numbers $k_1$, $k_2$, $k_3$, we may denote their greatest common divisor(gcd) by $\gcd(k_i,k_j)\equiv k_{ij}$ for gcd of a two pair of number $k_i,k_j$. ...
4
votes
1answer
37 views

powers of $f(x)$ where $f(x)\in\mathbb{Q} [x]\setminus\mathbb{Z} [x]$

Let $n\geq 2$ be an integer. If $f(x)\in\mathbb{Q} [x]\setminus\mathbb{Z} [x]$ can $f(x)^n$ be in $\mathbb{Z}[x]$ ?
1
vote
2answers
110 views

Does the equation $x^n\equiv 1\pmod p$ has at most $n$ solutions?

Does the equation $x^n\equiv 1\pmod p$, $p$ being a prime has at most $n$ solutions? If it does, how to show it? (I don't know a thing about fields.)
1
vote
3answers
54 views

Diophantine equations problem/exercise 3

Find all the pythagorean tripples (x,y,z) with x=40. Well I started with the known formulas for the pythagorean tripples but got me nowhere. Or I was not able continue the thought process required. I ...
2
votes
1answer
34 views

Diophantine Equations problem 2

Find all the solutions to the Diophantine equation x^2+y^2=2(z^2) .I do not have alot of expirience on Diophantine equations and i do not know how to approximate them.I can see that the tripples of ...
0
votes
2answers
39 views

Prime pairs ($p$, $q$) such that $p|q^m - 1$ for some integer $m$

Let $p$ and $q$ be two different prime numbers. Is it true that there exist an integer $m$ such that $p | q^m - 1$? If no, what family of prime pairs are known to have the above property?
0
votes
1answer
30 views

Hints regarding a “conjecture” about Pythagorean triples in a finite field.

My professor made the following "conjecture" in our elementary number theory course: $$\{(x, y, z) \in \mathbb{F}_p^3 : x^2 + y^2 = z^2\} = \{(x, y, z) \in \mathbb{F}_p^3 : x = 2st, y = s^2 - t^2, z ...
1
vote
1answer
52 views

What is known about the ramification index of ramified primes in an arbitrary cyclotomic extension of $\mathbb{Q}$

Let $\zeta$ be a primitive $m$th root of unity, and $L = \mathbb{Q}(\zeta)$. Then $B = \mathbb{Z}[\zeta]$ is the integral closure of $\mathbb{Z}$ in $L$. If $P$ is a prime ideal of $B$ and ...
0
votes
1answer
56 views

7-adic series expansion of square root of 2

Given the sequence $\{ a_n\}$ defined by the (positive and $a_n < 7^n$) solutions of the congruence $x^2 \equiv 2 \mod 7^n$ and $a_{n+1}\equiv a_n \mod 7^n$. e.g. the first one is $a_1 =3$ the ...
1
vote
1answer
56 views

Why doesn't SAGE understand reduced expressions mod p in a finite field extension?

Suppose I have a finite field $\mathbb{F}_{13}$ and I would like to adjoin an element, $\zeta$, with order $3$, since $\mathbb{F}_{13}$ does not contain one. So consider $\mathbb{F}_{13}(\zeta)$. Then ...
0
votes
1answer
42 views

A question of greatest common divisor

Let $a,b \in \mathbb{Z}$, where $a$ and $b$ are not both 0. Prove that $gcd(a,b)=1$ if and only if there exist $u,v \in \mathbb{Z}$ such that $au+bv=1.$ How can we prove this?
0
votes
2answers
20 views

When taking the square root of an adjoined element in a finite field, are both roots available?

Suppose I have the finite field $\mathbb{F}_8$ and I want to adjoin a number of order 8, $\zeta$, and consider the field extension $\mathbb{F}_8(\zeta)$. Then $\zeta^8 \equiv 1 \mod 8$ and so ...
1
vote
1answer
24 views

Question on Cardinality ..Help

a) Let $n$ be a positive integer. Define a relation on $\mathbb{Z} $, which yields a partition of $\mathbb{Z}$ with $n$ elements; and give the partition. b) Deduce that $n\omega = \omega$ where ...
2
votes
1answer
133 views

Quadratic reciprocity problem

How can I use quadratic reciprocity to prove that $-3$ is a quadratic residue $\pmod p$ if and only if $p=2$ or $p \equiv 1 \pmod 6$ and deduce that $\mathbb{Z}[\sqrt{-3}]/(p)\cong \mathbb{F}_p ...
1
vote
0answers
67 views

Is this theorem provable using relatively elementary number theory and abstract algebra?

$\textbf{Theorem}$: Let $p$ be a prime. Let $q$ be a prime that doesn't divide $p - 1$, so that $\mathbb{F}_p$ does not have an element of order $q$. Let $\zeta$ be an imaginary number whose order is ...
3
votes
1answer
38 views

$4|(p-1) \implies$ there is an element $x$ of order $ 4$ modulo $p$.?

"$p \equiv 1 \mod 4 \implies 4 \mid (p-1) \implies$ there is an element $x$ of order $4$ modulo $p$." I am having a difficult time understanding why this implies there is an element $x$ of order $4$. ...
3
votes
2answers
87 views

My professor says that this equation in a finite field has a solution but I don't think it does.

More than likely it is I who is mistaken, but is there a chance that my professor made a mistake in the following problem? We are tasked with: Let $p = 3$. We do not have an element of order $5$ in ...
2
votes
0answers
32 views

How do i prove that $\gcd(a_1,\ldots,a_n)\operatorname{lcm}(a_1,\ldots,a_n)=a_1\cdots a_n$?

Let $a_1,\ldots,a_n$ be nonzero integers. Define $$G=\{A\in\mathbb{Z}:A \text{ is a linear combination of } a_1,\ldots a_n\}$$ My definition for $\gcd(a_1,\ldots,a_n)$ is the principal ideal of $G$. ...
1
vote
1answer
33 views

Is there a generalization of the twin prime conjecture to rings or certain rings?

The question's in the title. For instance, if $R$ contains $2$ then there are an infinite number of pairs of prime principal ideals $(p),(q)$ such that $p = q + 2$. I just made that up and it's ...
1
vote
5answers
115 views

Is this a true theorem? [closed]

I'm trying to prove the existence of the following theorem: If $n,p \in \mathbb{N}$, then $(p+1)^n = 1 \mod p$ Is this theorem true? I think it is, but I don't know how to prove it! Thanks!
1
vote
2answers
41 views

Given a finite abelian group $G$ with $g \in G$, then for any divisor $d$ of $|g|$ there is an element of $G$ with order $d$.

From an homework question that comes as an introduction to abelian groups. Regarding my efforts to solve the question, I have been trying to utilize the fundamental theorem of finite abelian groups, ...