1
vote
0answers
30 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 ...
0
votes
2answers
38 views

Feedback on Euclidean Algorithm: $gcd(277, 301)$

Ans: $301 =277 \cdot 1 + 24$ $277 =24 \cdot 11 + 13$ $24 = 13 \cdot 1 + 11$ $13 = 11 \cdot 1 + 2$ $11 = 2 \cdot 5 + 1$ $2 = 1 \cdot 2 + 0$ Is this correct?
1
vote
4answers
87 views

If $d=\gcd(a+b,a^2+b^2)$, with $\gcd(a,b)=1$, then $d=1$ or $2$

Suppose $\gcd(a,b)=1$. Let $d=\gcd(a+b,a^2+b^2)$. I want to prove that $d$ equals $1$ or $2$. I get that $d\mid2ab$ but I can't find a linear combination that will give me some help to use the fact ...
2
votes
3answers
69 views

Find the remainder of $40^{314}$ divided by 91.

Here's what I have so far. $$x \equiv 40^{314} \mod{91}$$ $$\Rightarrow$$ $$x \equiv 40^{314} \mod{7}$$ $$ x \equiv 40^{314} \mod{13}$$ Then by FLT, $$40^6 ≡ 1 \mod{7}$$ $$40^{12} ≡ 1 \mod{13}$$ ...
1
vote
2answers
36 views

Find the largest $d \in \mathbb{N}$ such that for any $x \in \mathbb{N}$ the equation $16^x+10x-1 \equiv 0 \pmod d$

I interpret this problem as being finding the $gcd$ of the set of numbers generated by that given sequence. Checking by hand for a possible pattern in the sequence, I noticed instead that every term ...
1
vote
1answer
36 views

Finding the sixth roots of $-8i$

So to find the sixth roots of $-8i$, it would be equivalent to: $$z^6=-8i$$ So after all the math work, I end up getting my final answer to be: $$\sqrt2 \operatorname{cis}\left(\frac{\theta+2\pi ...
1
vote
1answer
53 views

How can I prove that this function is a bijection?

Show that the function $$ (\mathbb{Z}/ab\mathbb{Z})^\times \to (\mathbb{Z}/a\mathbb{Z})^\times \times (\mathbb{Z}/b\mathbb{Z})^\times $$ defined by $f([x]_{ab})=([x]_a,[x]_b)$ is a bijection where ...
1
vote
2answers
39 views

Prove that if m|a and m|b then m|a+b

I need help proving that if m|a and m|b, then m|a + b, and m|ac for any int c. I was thinking that m|a and m|b => a = km and b = lm. Thus a + b = km + lm = (k + l)m. Since this is a multiple of m ...
2
votes
3answers
79 views

Square root of a Mersenne number is irrational

Defining a Mersenne Number like this: k = $2^n -1$ I have to prove that the square root of a Mersenne number is irrational (has no solution in $\mathbb Q$). I know that it can be proven that the ...
0
votes
4answers
104 views

Find all $x \in \mathbb{N}$ such that $3^x -x \equiv 0 \pmod 7$

Initially I though this would be a simple application of Fermat's little theorem, as $a^{p-1} \equiv 1 \pmod p$ can be more generally stated as $a^p \equiv a \pmod p$. However, trying to apply that ...
0
votes
1answer
44 views

Is it possible to prove the existence of an integer with given order while not finding the value itself?

The original question is here: (a)Show that there is an integer a mod 249 whose order is 82. [Hint: If h = ord_m(a), k = ord_n(a) and (m, n) = 1, then ord_mn(a) = [h, k]. ] (b) Show that there is ...
4
votes
1answer
75 views

How can I prove that $\frac{\sigma(n)}{n} = \sum_{(d|n)} \frac{1}{d}$ for every $n \in \mathbb{Z^{+}}$?

I want to show that $\displaystyle \frac{\sigma(n)}{n} = \sum_{(d|n)} \frac{1}{d}$ for every $n \in \mathbb{Z^{+}}$. This is essentially a basic number theory question. I am able to get to the ...
0
votes
0answers
61 views

Is my proof good enough?

Prove: The product of any three consecutive natural numbers is divisible by 6. 6|n (n+1) (n+2). If n is an odd number (n=(2 t+1), t is any natural number), then (n+1)= ((2 t+1)+1) an even number. So ...
0
votes
5answers
105 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
39 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, ...
0
votes
3answers
48 views

If $a,b < p$, then $p \nmid ab$?

I'm trying to prove that if there two positive integers $a$ and $b$ such that they are less than a prime number $p$, then the product $ab$ will not be divisible by $p$. I know there must be multiple ...
0
votes
1answer
15 views

Properties of a Jacobi sum for $p=1\bmod 4$

I'm struggling with Ireland and Rosen, chapter 8, exercise 7. Suppose that $p=1\bmod 4$ and that $\chi$ is a character of order 4. Write $\chi^2=\rho$ a character of order 2. Show that ...
1
vote
1answer
102 views

Quick question on abundant numbers

is this correct? 1) Show that if $\sigma (n) > 2n$ it follows $ \sigma (kn) > 2(kn)$. Proof: $\sigma (kn) \ge \sum_{d|n} kd = k\cdot \sigma(n) > k2n = 2kn$. How can I show $\sigma (kn) ...
0
votes
2answers
34 views

How can I prove this relation between primes and congruences?

Suppose that $p$ is a prime, and $a\equiv b(\bmod~p)$. Prove that $$a^p\equiv b^p(\bmod~p^2)$$ So, from the first statement, we know that $p|(a-b)$ and that $[a]_p = [b]_p$. Bringing this over to ...
1
vote
2answers
54 views

Find all $n$ such that if $\gcd(a,n)=1$ then $a^2=1$ mod $n$

I really have no idea where to start with this question: Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$ I found out that it works for $n = 8$, since all odd numbers modulo 8 have order ...
0
votes
1answer
27 views

Equivalent definitions of the quadratic gauss sum

In Ireland and Rosen, the quadratic Gauss sum of $a$, $g_a$, is defined by $g_a=\sum_{t=0}^{p-1}(\frac tp)\zeta^{at}$ with $\zeta$ a $p$th root of unity, $p$ an odd prime and $(\frac\cdot\cdot)$ the ...
1
vote
2answers
167 views

Determine all complex numbers z in equation:

Let $n\in\mathbb{N}$. Determine all complex numbers $z\in\mathbb{C}$ such that $z^{n-1}$ = $\bar{z}$ How would I begin this? Would I begin by saying $z=a+ib$ and expand and stuff?
3
votes
0answers
46 views

Josephus Variant

I set myself the challenge of trying to solve a variant of trying to solve a variant of the josephus problem where instead of killing every second person, every third person dies. The formula for the ...
0
votes
3answers
53 views

No primitive root modulo $2^n$ for $n\ge 3$

Prove that there is no primitive root modulo $2^n$. I'm not sure how to begin proving this. I know $\varphi(2^n)=2^{n-1}$, thus a primitive root $a\in\left(\dfrac{\mathbb{Z}}{2^n\mathbb{Z}}\right)^*$ ...
1
vote
1answer
31 views

Computing the Legendre symbol of -3, $(\frac{-3}p)$

I'm working on Ireland and Rosen, exercise 6.8. Let $\omega=e^{2\pi i/3}$ satisfying $\omega^3-1=0$. Show that $(2\omega-1)^2=-3$ and use this result to determine $(\frac{-3}p)$ for $p$ an odd ...
3
votes
4answers
68 views

Can anyone prove for every $a,b \in \mathbb Z^+ < p$ ( $p$ is a prime), $p \nmid ab$?

Can anyone prove for every $a,b \in \mathbb Z^+ < p$ ( $p$ is a prime), $p \nmid ab$? I was trying my best to do the problem but like I don't know where to start or anything!
0
votes
2answers
47 views

Find the smallest possible integer $k$ such that $8|7^{348}+2^{5605}+k$

$$ \text{Find the smallest possible integer } k \text{ such that } \\ 7^{348}+2^{5605} +k \text{ which is divisible by } 8 \text{ given that } $$ a≡b mod n⇒a^m≡b^m mod n okay, I understand that $a ...
1
vote
0answers
52 views

Reason behind the given claim?

Let $N$ denote a set containing numbers from $1$ to $n$. suppose $N = 3$, then $$F(3) = (1) + (2) + (3) + (1+2) + (1+3) + (2+3) + (1+2+3) = 24$$ $$F(4) = 80$$ Thus $F(N)$ represents the sum of all ...
-2
votes
1answer
36 views

How do I solve the following Diophantine equation using Congruences?

I'm given: $4x+51y=9$. I am given a hint that when we use $4x=9 \pmod{51}$ we get $x = 15 + 15t$, and also if we use the congruence $51y=9 \pmod 4$ we get $y=3+4s$. They say it's handy to then find ...
1
vote
0answers
56 views

Asymptotic estimate of coprime pairs of integers $\leq n$.

Let $M_{n} = \{(x,y) \in [n] \times [n]: xy \leq n^{2} \text{ and } gcd(x,y) = 1\}$, where $[n] = \{1, 2, \dots , n\}$. In other words, let $M_{n}$ be the set of pairs of coprime integers both $\leq ...
4
votes
1answer
76 views

Show that if $n$ is is a positive integer such that $n\ne 2$ and $n\ne 6$ then $\phi(n) \ge \sqrt n$

$\phi(n)$ being Euler's totient function. Regarding effort put into the problem: In the case that $n$ is a prime $p$, then it is given that $\phi(p) = p-1$. It is also given that $n\ne 2$, so the ...
0
votes
1answer
52 views

Prove that $\mu(a, b)= \mu(1, b/a)$.

Let $n$ be a positive integer and consider the partially ordered set $(X_n, \;|\; )$, where $X_n = \{1, 2, ... ,n\}$ and the partial order is that of divisibility. Let a and b be positive integers in ...
3
votes
4answers
47 views

Number of triplets adding to a certain number

Suppose I have $L$ and $m$ in $\mathbb{N}$. What is the cardinality of the set $$ \{ (x_1, x_2, x_3) \in \mathbb{N}^3 : x_1 + x_2 + x_3 = L, x_i > m \}? $$ An exact number would be great but I ...
5
votes
2answers
65 views

If $1 \sim 2$ and $2 \sim 3$, how is $\sim$ an equivalence relation?

I'm asked to describe an equivalence relation on $S \in \{1,2,3,4\}$ where $1 \sim 2$ and $2 \sim 3$. However I'm a little confused over why this qualifies as an equivalence relation, since through ...
1
vote
1answer
101 views

RSA Ciphertext Message.

Hey I'm really stuck and I have to finish soon. Part A Ray, Sam and Todd are lazy, and they have set up their RSA public keys as $(3,nR),(3,nS),(3,nT)$ respectively. We may assume that any two of ...
0
votes
1answer
30 views

$p$ is an odd prime of the form $p=x^2+2y^2$ iff $p\equiv_8$ $1$ or $3$ [duplicate]

How would I prove the following: Show that an odd prime $p$ can be written on the form $p=x^2+2y^2$ for some $x,y\in\mathbb Z$ iff $p\equiv_8 1, 3$. Hint: use the quadratic reciprocity and the ...
0
votes
1answer
25 views

If m divides n, prove that a^m-b^m divides a^n-b^n.

To make a long story short, I have a two part homework in an elementary number theory course I'm currently doing at uni. First part is to prove that $(a-b)$ divides $(a^n-b^n)$ with $a,b ...
0
votes
5answers
110 views

What are Fibonacci numbers

I am aware of the sequence but not the pattern 0,1,1,2,3,5,8..... If someone could explain the pattern they follow, that would be a lot of help. I do understand they are in nature, but I am not ...
4
votes
2answers
58 views

Show that there are exactly four solutions to $ x^{4} \equiv 1$ mod $ p^{n} $

in $\mathbb{Z}/p^n$ where $ p \equiv 1 $ mod $ 4 $ I have been told as a 'hint' to use the isomorphism $\mathbb{Z}/p^n \cong \mathbb{F}^\times_{p} \times \mathbb{Z}/p^{n-1}$ but I don't understand ...
0
votes
0answers
19 views

Problem on Counting Points in a Lattice

I am reading a proof and am getting caught up on this one step. For context let $D$ be a bounded open set in the first quadrant of $\mathbb{R}^2$ and let $RD = \{(x,y) \in \mathbb{R}^2 : ...
3
votes
1answer
39 views

Identity Involving Cyclotomic Polynomials

Let $m > 1$ and let $p$ be a prime not dividing $m$. If $\Phi_*$ denotes that $*$th cyclotomic polynomial, then establish the following identity: $$\Phi_{pm}(x) = \frac{\Phi_m(x^p)}{\Phi_m(x)}$$ ...
0
votes
2answers
53 views

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation?

Is $a \sim b$ such that $\gcd(a,b) > 1$ an equivalence relation? I know that it's reflexive, since $\gcd(a,a) > 1$. It's also symmetric since $\gcd(a,b) > 1$ iff $\gcd(b,a) > 1$. ...
0
votes
2answers
53 views

Proving $\prod_{i=1}^n (\frac{1}{i} + 1) = n+1$

Prove using a direct proof that $$\prod_{i=1}^n \left(\frac{1}{i} + 1\right) = n+1$$ Okay, so I think I have done it correctly using an inductive proof: Base case: $(1+\frac11)=2$, ...
2
votes
2answers
39 views

Prove that if $(u,v)$ is chosen randomly from $S$, there is at least a $50\%$ chance that $u\ne\pm v \bmod N$

I need serious help with this problem. Suppose $N$ is an odd composite number and $S=\{(x,y) \in \mathbb Z^2 : x^2 \equiv y^2 \mod N\}$ Prove that if $(u,v)$ is chosen randomly from $S$, there is ...
2
votes
2answers
55 views

question on Floor function: $[na] = [a]n?$

let $n\in \mathbb{N}, a \in \mathbb{R}$. What can I then say about the gauß-function or floor-function: $[an]$ ? I have to show: $\left[\frac{[na]}{n}\right] = [a] := max\{ z \in \mathbb{Z}: z \le ...
0
votes
1answer
15 views

Find integers $t,z$ satisfying $(a+b)z+abt=1$ [duplicate]

Let be $a,b,u,v$ integers and $au+bv=1$. I have to find integers $t,z$ satisfying $(a+b)z+abt=1$. I think I can solve it by congruence. What do you think? I realised $$bz\equiv 1 \quad (\text{mod}\, ...
1
vote
0answers
49 views

Rigorous proof writing

I'm a little bit confused about this problem "Suppose that $m_1, m_2, ..., m_r$ are pairwise relatively prime positive integers. For each j, let $C(m_j)$ denote a complete system of residues mod ...
-1
votes
2answers
64 views

how to find nth term of different fibonacci series with golden ratio [duplicate]

what i know : if i want to find $Nth$ term of a fibonacci series like : 1 1 2 3 5 8 13 21 ....... then to find $6th$ term we use golden ratio ...
1
vote
2answers
30 views

Abstract Algebra/Elementary Number Theory Computation

Compute $2^{2^{17}}+1$ mod $19$. (hint: compute first $2^{17}$ mod $18$) Using the fact that there are $6$ numbers coprime to $18$, I got that $$2^{17}\; \mathrm{mod}\;\; 18 = 2^6 \cdot 2^6 ...
4
votes
1answer
63 views

Find all primes $p,q$ such that $p^q + q^p$ is perfect square

Just a hint for a solution? I tried to separate the cases when one of the primes is 2,so it would be $2^p + p^2 = k^2$,for some k.Since $2^p$ is even,and $p^2$ is odd,it implies that $k^2$ is ...