0
votes
2answers
73 views

What does “finding an element” in $\mathbb Z_n$ mean?

I am currently in my last year of high-school and I try to learn Algebra on my own, one of my textbook exercise ask me to Find elements: $$ ...
0
votes
2answers
53 views

Greatest Common Denominator and linear combination

I know the gcd of 616 and 427 is 7, but I know need to do a linear combination of it. So there exists $x, y$ such that $$7=616x+427y$$ How do I solve for x and y?
1
vote
1answer
102 views

Let $p \geq 2$. Prove that if $2^p-1$ is prime then $p$ must also be prime.

Would the following be a valid proof? Let $r$ and $s$ be positive integers, then the polynomial $x^{rs}-1=(x^r -1)(x^{s(r-1)}+x^{s(r-2)}+\cdots+x^r+1)$. So if $p$ is composite (say $rs$ with ...
2
votes
5answers
78 views

Show that lcm$(a,b)= ab$ if and only if gcd$(a,b)=1$

Not sure how to begin. If gcd$(a,b)=1$ what can I deduce from that?
6
votes
3answers
122 views

$x^p - 1$ always have a factor congruent to $1$ modulo $p$? [closed]

I was doing some group theory analysis and found the above statement. can you disprove it? I am not sure with my work, I am new with Group Theory. p is an odd prime [Editor's Comment] My ...
4
votes
1answer
58 views

Show that each integer of the form $a^2+b^2$ has all the factors of this form, where $(a, b)$ are distinct integers and relatively prime

Show that each integer of the form $a^2+b^2$ has all the factors of this form, where $(a, b)$ are distinct integers and relatively prime Progress If $a^2+b^2$ is prime then it is already proved, ...
2
votes
0answers
40 views

How to prove: $pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$

For any two distinct primes $p, q$ there is a unique integer $k$ such that: $$pq=\binom{k}{q}-\binom{p}{q}-\binom{k-p}{1}+1$$ Where $k$ is the smallest integer greater than $p$ that is relatively ...
0
votes
2answers
66 views

if $m$ and $n$ relatively prime integers different from $\pm 1$, there are unique integers $u$ , $v$ $\in Z$ such that $um+vn=1$ and $0 \le u \lt |n|$

Let $m$ and $n$ be relatively prime integers different from $\pm 1$. Show that there are unique integers $u$ , $v$ $\in Z$ such that $um+vn=1$ and $0 \le u \lt |n|$. In this case show that $|v| \lt ...
2
votes
3answers
69 views

Finding the square root $s$ of 1293 modulo 3337.

If $3337 = 47 \cdot 71$, how do you find the square root $s$ of $1293 \pmod { 3337}$ (where $0 < s < 3337$). I understand that $m = 3337 = p \cdot q$ and $p=47$ and $q=71$, but not sure where ...
9
votes
0answers
172 views

When is $(x^n-1)/(x-1)$ a prime number?

Let $x > 1$ and let $n$ be a prime. I'm wondering if a characterization of this is known. That is, what are sufficient and necessary conditions for $$ \dfrac{x^n-1}{x-1} = 1 + x + x^2 + \cdots + ...
6
votes
1answer
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$?
6
votes
4answers
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 ...
-1
votes
1answer
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!
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
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 ...
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
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 ...
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
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 ...
1
vote
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 ...
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
76 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
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
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
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 ...
1
vote
3answers
107 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
75 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
23 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
49 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
11 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
39 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
43 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
38 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
111 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
58 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
36 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
40 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
32 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
54 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
61 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
62 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
45 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
21 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
27 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 ...