Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.
0
votes
1answer
35 views
Question regarding Legendre symbol and Quadratic reciprocity.
How would determine the value of the following Legendre symbol is $1$ or $-1$?
$$\left(\frac{\frac{p - 1}{2}}{p}\right)$$
So far, I've been able to figure out this much:
$$\left(\frac{p - ...
1
vote
1answer
47 views
Looking for name of theorem: “rational $\Leftrightarrow$ fractional part terminates or repeats”
I am looking for the name of the theorem that says that a number $x$ is rational if and only if its fractional part terminates or repeats (where "fractional part" refers to the representation of $x$ ...
3
votes
3answers
45 views
Solving for Modular arithmetic
Solve the equation $38z\equiv 21 \pmod {71}$ for z.
Little confused by the questions. My attempt is: $38 \odot z = 21.$ Then find the inverse of 38 from mod 71 and multiply both sides. Lastly, take ...
3
votes
2answers
36 views
Does there exist an integer $x$ satisfying the following congruences?
Does there exist an integer $x$ satisfying the following congruences?
$$10x = 1 \pmod {21} \\
5x = 2 \pmod 6 \\
4x = 1 \pmod 7$$
I was trying to do this by following way but failed to get an ...
2
votes
5answers
51 views
If $p$ be a prime and r be any integer, $0 < r < p$ then $\frac{(p-1)!}{r!(p-r)!}$ is an integer.
Let $p$ be a prime and r an integer, $0 < r < p$. Show that $\frac{(p-1)!}{r!(p-r)!}$ is an integer.
The given number is $ \frac{\binom {p} {r}}{p}$. after tha how can I show that$p$ divides ...
5
votes
2answers
165 views
Does there always exist an odd number of elements?
Given a nonzero integer $k$, does there always exist a positive integer $n$ such that there are exactly an odd number of elements $i\in\{0,1,...,n-1\}$ with $\frac{2^n-1}4 < 2^ik \mod{2^n-1} < ...
5
votes
1answer
86 views
Express an even number as a sum of primes
Show that every even natural number grater than $2$ can be expressed as a sum of two prime numbers.
No idea how to prove this. Can you help? thanks
1
vote
3answers
64 views
question in number theory
Let $p$ is an odd prime and $n$ is an even natural number. It is clear that $2$ divides $p^n+1$. I would like to know Is the following claim true?
$4$ does not divides $p^n+1$.
3
votes
2answers
35 views
Prove that $( \frac{l}{(l,m)},\frac{m}{(l,m)}) = 1$ [duplicate]
Prove that $( \frac{l}{(l,m)},\frac{m}{(l,m)}) = 1$, given that $l, m \in \Bbb{N}$. I had this question on my number theory final that I took earlier today. This was the second part of a 2 part ...
1
vote
2answers
51 views
Prove if $(l,m)=1$ and $l\mid mn$, then $l\mid n$.
I just took my number theory final and this was on the exam as the second question. It said to use the canonical decomposition of $l, m$ and $n$ for the proof. This is what I put down on the exam:
...
5
votes
4answers
123 views
How to factor 5671?
The other day I wanted to factor 5671 in my head. (It turns out to be $53\cdot107$, but I did not know this at the time.) I quickly ruled out the easy divisors, 2, 3, 5, 7, 11, and 13. At this point ...
1
vote
3answers
45 views
Primitive Roots
Given $p$, $q$ both primes such that $q = 2p + 1$, I need to prove that $-4$ is a primitive root mod $q$.
So far haven't found a direction that could lead me to the solution.
Any suggestion or short ...
1
vote
2answers
72 views
A new prime divides $a^p+1$
Let $a\in \mathbb{Z}$ and $p, q\in\mathbb{P}$. If $q\mid a+1$, there exists at least a prime $r \neq q$ such that $r\mid a^p+1$ (except for some trivial cases).
1
vote
3answers
100 views
If a relation is reflexive is it symmetric and transitive?
If a relation is reflexive is it symmetric and transitive ?
let ~ means " in relation with "
if A is a set , ~ is a relation on $A$, prove that:
if $a$~$a$ for any $a$ $\in$ A then
1- $x$~$y$ ...
1
vote
1answer
33 views
Why is $\sum_{d \mid N} N/d ϕ(N/d) ϕ(d) = N^2 \prod_{p \mid N} (1 - 1/p^2)$?
In the end, given the Euler totient function $ϕ$, I want to understand why:
$$ \sum_{d \mid N} (N/d) ϕ(N/d) ϕ(d) = N^2 \prod_{p \mid N} (1 - 1/p^2)$$
Do you have any hints regarding this?
...
2
votes
2answers
52 views
$\frac{1}{ab}=\frac{s}{a}+\frac{r}{b} \overset{?}{\iff}\gcd(a,b)=1$
$$\frac{1}{ab}=\frac{s}{a}+\frac{r}{b} \overset{?}{\iff} \gcd(a,b)=1$$
This seems almost painfully obvious because it is just $ar+bs=1$ in another form. This second form is the definition of ...
1
vote
1answer
29 views
finding a primitive root.
It says for part A to Find a primitive root r of 38? Im not sure if I did it right.
I first calculated $\phi(38)=\phi(19*2)=18$. So there are 18 numbers that are relatively prime to 38. Listing them ...
1
vote
1answer
55 views
Does $a \mid bc$ imply $\frac{a}{(a,b)} \mid c$?
If $a \mid bc$, then does $\frac{a}{(a,b)} \mid c$? I doubt anybody here is industrious enough to show this via a diagram, but who knows.
-1
votes
5answers
69 views
$(a,m) = (b,m) = 1 \overset{?}{\implies} (ab,m) = 1$
In words, is this saying that since $a$ shares no common prime factors with $m$ and $b$ shares no common prime factors with $m$ too, then of course the product of $a$ and $b$ wouldn't either!?
2
votes
1answer
56 views
Solving the equation for $x$ in $Z_n$
How do you solve for x in the the $Z_n$ specified? For example, for the equation:
1) $3\odot x\oplus8\equiv1(\rm{mod} 10)$ or
2) $342\odot x\oplus 448\equiv73(\rm{mod}1003)$
How would you solve for ...
4
votes
1answer
82 views
(USAJMO)Find the integer solutions:$ab^5+3=x^3,a^5b+3=y^3$
Find the integer solutions:
$$a·b^5+3=x^3,a^5·b+3=y^3$$
This is the first problem of today's USAJMO (has finished),I only find a trival result that $x\equiv y \pmod6$ and $abxy≠0 \pmod 3$.
Thanks in ...
3
votes
6answers
95 views
$11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$
Problem
So, I am to show that $11$ divides $10a + b$ $\Leftrightarrow$ $11$ divides $a − b$.
Attempt
This is a useful proposition given by the book:
Proposition 12. $11$ divides a ...
4
votes
5answers
155 views
How to show that $a$ can be divided by $6$ if and only if it can be divided by both $2$ and $3$?
Prove that for: $a \in\mathbb Z$, $a$ is divisible by 2 and $a$ is divisible by 3 if and only if $a$ is divisible by 6.
EDIT: Sorry, I wasn't aware of how exactly this site worked. This is pretty ...
0
votes
1answer
41 views
what is a simple way to find the outliers of an array
Say I have the following array of integers, I wonder if there is a simple way to identify the outlier, which is 58 here.
[15, 17, 19, 16, 14, 58]
-2
votes
1answer
66 views
Finding a primitive root modulo $13$ [duplicate]
Find a primitive root modulo each of the following integers.
a) $13$
My TA said we are not going to go over this. We did not go over the topic. It seems like something good to know though.
...
1
vote
2answers
36 views
Determine number of squares in progressively decreasing size that can be carved out of a rectangle
How many squares in progressively decreasing size can be created from a rectangle of dimension $a\;X\;b$
For example, consider a rectangle of dimension $3\;X\;8$
As you can see, the biggest square ...
1
vote
1answer
69 views
Finding a primitive root modulo $11^2$
Find a primitive root modulo each of the following moduli:
a) $11^2$
My TA said he is not going to go over this so do not worry about it. He said you can try this if you want but he would ...
2
votes
6answers
104 views
Finding the remainder when $2^{100}+3^{100}+4^{100}+5^{100}$ is divided by $7$
Find the remainder when $2^{100}+3^{100}+4^{100}+5^{100}$ is divided by $7$.
Please brief about the concept behind this to solve such problems. Thanks.
1
vote
1answer
42 views
Two relations involving the gcd
This is part of a bigger problem I am solving. Let $k\ge 2$ be a fixed positive integer. Is it possible to find an integer $v, v>k$ such that ...
3
votes
1answer
121 views
Prove that there exist infinitely many squares $a$ such that $\sqrt{\sqrt{a}}$ is a square
I was just thinking about squares while randomly punched numbers into my calculator and I was wondering do there exist infinitely many squares such that $\sqrt{\sqrt{a}}$ is a square and $a$ is also a ...
2
votes
1answer
54 views
how to show associativity of multiplication for not just 3 operands but for n operands
ie Id like to show
a(bc)=(ab)c
but for any n operands
eg
abcdefg=gfdcabe etc
I can see this is very intuitive that this should be true for all n operands, but as a logical exercise I would like to ...
15
votes
5answers
844 views
Intervals that are free of primes
How can I prove that exists intervals as large as I want that are free of primes?
I mean, $\forall \ k \in \mathbb{N}, \exists \ k$ consecutive positive integers none of which is a prime.
-4
votes
1answer
43 views
least non-negative residue of $a^{67}$ modulo $7$
My professor might accept C++ code to show that for $0 ≤ a ≤ 6$, the least non-negative residue of $a^{67}$ modulo $7$ is $a$.
2
votes
4answers
87 views
How do I show that $6(4^n-1)$ is a multiple of $9$ for all $n\in \mathbb{N}$?
How do I show that $6(4^n-1)$ is a multiple of $9$ for all $n\in \mathbb{N}$? I'm not so keen on divisibility tricks. Any help is appreciated.
0
votes
1answer
25 views
Is the “least non-negative residue” of $b^p \pmod{m}$ just $b^p \pmod{m}$?
I'm just wondering if the "least non-negative residue" of $b^p \pmod{m}$ is just $b^p \pmod{m}$ itself. What is the "least non-negative residue"? How is it found? Is this how it is found? Just by ...
3
votes
1answer
76 views
Why don't I end up with the same splitting field?
I've understood that the splitting field of $x^4+2$ and the splitting field of $x^4-2$ over $\mathbb{Q}$ are both the field $\mathbb{Q}(\sqrt[4]{2} , i)$. With degree $8$ over $\mathbb{Q}$. This ...
-2
votes
1answer
32 views
Modular Arithmetic: Least Non-negative Residues
I am to compute the least non-negative residue of $4^n \pmod{9}$ for $n = 1, 2, 3, 4, 5, \dots$
I must also prove that $6 · 4^n ≡ 6 \pmod{9}$ for every $n > 0$.
0
votes
4answers
126 views
Calculations by Hand
Find the least non-negative residue of:
(i) $5^{18}$ mod $11$
(ii) $68^{105}$ mod $7$
(iii) $4^{47}$ mod $12$
(iv) $66^{75}$ mod $19$
C++ code failed... I'm trying to do by hand now. Maple has ...
5
votes
1answer
59 views
For which $a$ is $n\lfloor a\rfloor+1\le \lfloor na\rfloor$ true for all sufficiently large $n$?
Inspired by this question I ask this. For which $a$ is $n\lfloor a\rfloor+1\le \lfloor na\rfloor$ true for all sufficiently large $n$?
The original question concerned $a=e$, the usual ...
2
votes
1answer
30 views
$15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$
For which numbers $a$ is it true that if $15a ≡ ca \pmod{25}$, then $15 ≡ c \pmod{25}$?
I know that this means that $a\frac{15-c}{25}=k_1\in \mathbb{Z}$ and $\frac{15-c}{25}=k_2\in \mathbb{Z}$, but ...
6
votes
6answers
183 views
Representing the function $\mathbb Z_9\to\mathbb Z_9$, $f(0) = 1$, $f(1) = \ldots = f(8) = 0$ as a polynomial in $\mathbb Z_9[x]$
Let $\mathbb Z_9=\left\{0,1,2,3,4,5,6,7,8\right\}$ be the set of integers modulo 9 and $f:\mathbb Z_9 \rightarrow \mathbb Z_9$ be a function.
Assume $f(0)=1$, $f(1)=f(2)=...=f(8)=0$. What is the ...
2
votes
2answers
52 views
Order of a group?
Let $a = g^{16}$. Assume $\operatorname{ord} g = 40$. Find $\operatorname{ord} a$.
Not sure how you would find $\operatorname{ord}a$. We did not go over this. Here is what I did
We know that ...
0
votes
0answers
31 views
Show that $ {\overline a }$ is an inverse of a modulo n, then $ord_n$a = $ ord_n{\overline a }$.
Show that $ {\overline a }$ is an inverse of a modulo $n$, then $\text{ord}_n$a = $ \text{ord}_n{\overline a }$.
Here is the proof I did:
That $\text{ord}_na = \text{ord}_n{\overline a }$. follows ...
0
votes
4answers
118 views
$(a,b)=d \overset{?}{\implies} (a^3,b^3)=d^3$
Why is this true? I suspect that its because $\frac{LCM(a,b)^3GCD(a,b)^3}{b^3}=a^3$ and $\frac{LCM(a,b)^3GCD(a,b)^3}{a^3}=b^3$, so it must be the case for $LCM(a,b) \notin R(a,b)$, right?
1
vote
0answers
25 views
Quadratic Equation Modulo an even composite
I am familiar with using the quadratic formula and Tonelli-Shanks with Hensel's Lifting Lemma to solve a quadratic equation, but how do I solve a quadratic equation in an even modulus? I can't use the ...
9
votes
1answer
154 views
How to find all integers $a,b > 1$ satisfying $b \mid a^2+1$ and $a^2 \mid b^3+1$?
Let $a,b\in \mathbb{Z}$ with $a,b>1$, and such that $b \mid a^2+1$ and $a^2 \mid b^3+1$. Find all such $a,b$.
I found $a=3,b=2$. Are there any other solutions? Thank you.
yesterday I have ...
6
votes
1answer
138 views
Two questions re: $\sum_{n=1}^{\infty}n^{-p_{n}}$
Edit Motivation for question: I looked up the decimal expansion of:
$$\sum _{n=1}^{\infty } \sum _{k=n}^{\infty } k^{-2 k},$$
which matches the first seven digits of the function in question. I would ...
3
votes
5answers
140 views
Revisted: GCD - $(a,c)=1=(b,c) \overset{?}{\implies} (ab,c)$
How should I show that if $(a,c)=1=(b,c)$ then $(ab,c)$?
How should I show that if $a|bc$ and $(a,b)|c$, then $a|c^2$. I think I have the answer, but I'm not sure.
1
vote
1answer
78 views
Finding integers to satisfy two inequalities.
Let $a,b,c $ be integers. We want to prove that there exists some integers $r,u,s,t$ such that $ru-st=1$ and $$|2art+b(ru+ts)+2csu|\le |ar^2+brs+cs^2|\le |at^2+btu+cu^2|$$
This problem is from: ...
0
votes
1answer
45 views
Linear Diophantine Equations: Integer Solutions $x,y$ exist for $ax+by=c$, but how do I find them by hand?
I'm trying to find which of $133x+203y=38$, $133x+203y=40$, $133x+203y=42$, and $133x+203y=44$ have integer solutions. I know that only the third equation suffices for these conditions because ...
