0
votes
1answer
32 views

Prove there exists a unique polynomial

I'm having trouble proving the following lemma: Let $ p $ be a prime and $ f \in \mathbb{Z}_p [x_1, \dots, x_n] $. Prove there exists a unique polynomial $ f^* \in \mathbb{Z}_p [x_1, \dots, x_n] $ ...
2
votes
1answer
34 views

Subgroups of $ \mathbb{Z}^n $

I'm having a difficulty proving the following: Let $ H \leq \mathbb{Z}^n $ be a subgroup. Prove that $ H \simeq \mathbb{Z}^k $, $ k \leq n $. Moreover, prove that if $ H = \{(c_1, \dots, c_n) \in ...
3
votes
3answers
29 views

Let $G = \text {Gal}(L/K)$. How do I see that $\phi \in G$ is completely determined by $\phi\mathbb( \sqrt[4] {3})$ and $\phi(i)$?

Let $K = \mathbb Q$ and $L = \mathbb( \sqrt[4] {3}, i)$. I see that $L \supset K$ is a an Galois extension. Also, after computations I've $[L : K] = 8$ (degree of $L$ over $K$ considered as a vector ...
2
votes
0answers
111 views

The congruence $\{(a^m, a^{m+r})\}^\#$ on $a^+$.

I've spent a bit too long on this exercise. It's time to ask for help. This is Exercise 1.20 of Howie's Fundamentals of Semigroup Theory. Let $\rho_{m, r}$ (for $m, r\ge 1$) be the congruence ...
1
vote
2answers
39 views

Prove that $[a]$ and $[n]$ are not relatively prime if and only if there is a nonzero element $[b] \in \Bbb{Z}_n$ such that $[a][b] = 0$

Here is my attempt (1) ---> First of all I know that $[n] = [0]$ and then we assume that a and n are not relatively prime then there exists an integer $x = \gcd(a,n)$ and $x \neq 1$ and so there ...
2
votes
8answers
125 views

Find the last two digit of $3^{3^{100}}$.

Find the last two digit of $3^{3^{100}}$. I know how to calculate if I have $3^{100}$. That I will use euler's theorem. which gives me $3^{40}\equiv 1 \pmod{100}$. And so on... but if I have ...
0
votes
0answers
16 views

Solving $-\alpha x^2-\beta y^2-\alpha\beta z^2=-p$ to check for isomorphism of quaternion algebras.

Edited I am considering quaternion algebras $(-\alpha,-\beta)_\mathbb Q$, with $\alpha,\beta>0$. I am trying to find several of these, which are not isomorphic. I do not want to digress into ...
0
votes
1answer
31 views

if ca ≡ cb mod n and d = (c,n) where n = dm . prove that a ≡ b mod m

if $ca \equiv cb \ (\textrm{mod}\ n)$ and d = (c,n) where n = dm , prove that $a \equiv b \ (\textrm{mod}\ m)$ so here is my attempt from $ca \equiv cb \ (\textrm{mod}\ n)$ we know that n | ca - ...
1
vote
3answers
57 views

Are there any nonzero integers $a$ , $b$ such that $a^2$ = $3b^2$

I know since 3 is prime then nothing divides 3 except 3 and also 3 is a factor for only multiples of 3. $a^2$ must be a multiple of 3. But I am kinda stuck here.
2
votes
1answer
43 views

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$?

Is it true that if $\gcd(a,b) = 1$ and $\gcd(a,c) = 1$ then $\gcd(ac,b) = 1$? I know that $\gcd(a,b) = 1$ means that there exist integers $m$ and $n$ such that $am + bn = 1$ Same thing for ...
6
votes
2answers
298 views

Novel approaches to elementary number theory and abstract algebra

As a part of a university course, I'll have to study Herstein's Topics in algebra and Hardy&Wright's Introduction to the theory of numbers. Can you suggest some books (to be used as companions) ...
0
votes
1answer
38 views

Hilberts Theorem (norm group)

The theorem says the following: The map $N$ is a group homomorphisim from the multiplicative group of $\mathbb{Q}^{x}[i]$ to the multiplicative group of $\mathbb{Q}^{x}$ and has kernel $\lbrace ...
0
votes
1answer
45 views

If $\gcd (a,0)=1),$ what can a possibly be?

I feel like a could be any number, but $0$ could divide any number,so they won't be mutually exclusive. I'm not sure, maybe this is not related, but it just confused me.
0
votes
2answers
81 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
59 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
106 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
91 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
123 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
59 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
41 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
184 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
283 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
31 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
64 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
32 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
32 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
159 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
62 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
42 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
79 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
42 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
43 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
109 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
76 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
50 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
40 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 ...