Questions on congruences, linear diophantine equations, greatest common divisor, divisibility, etc.

learn more… | top users | synonyms

1
vote
2answers
43 views

Can't understand source of constant for prime counting function:

Consider the prime counting function $$ \pi(x) = \ the \ number \ of \ primes \ less \ than \ or \ equal \ to \ x$$ It is well known due to the sieve eratosthenes that given an integer $n$ and the ...
1
vote
4answers
42 views

Wilson's Theorem textbook proof question

I'm trying to understand this proof from Stein's Elementary Number Theory, and I understand the pairing of inverses but not the other direction. I have two questions: $1).$ When the proof says, $l$ ...
3
votes
2answers
264 views

Is $a^b+b^a$ unique for all integers a and b?

Is $a^b+b^a$ unique for all integers $a$ and $b$? Any proof?
1
vote
3answers
47 views

First index of number in that arithmetic progression which is a multiple of the given prime number

I have a prime number $p$, an arithmetic progression starting at $a$ with common difference $d$. How to find the first index of a term in that arithmetic progression which is a multiple of the given ...
3
votes
0answers
69 views

On the indivisibility of odd perfect numbers by small numbers

A good day to everyone! This question is an offshoot of the following MSE posts: Odd perfect number divisors Can an odd perfect number be divisible by $101$? My question is as follows: Is ...
11
votes
6answers
2k views

If an inequality is true for all natural numbers, is it necessarily true for all real numbers inbetween?

A lot of the time in lectures, my professors prove (by induction) an inequality (e.g. $(1+x)^n \geq 1+nx$) in the natural numbers (or any subsets thereof), and I've noticed (not rigourously; only by ...
5
votes
2answers
132 views

When is $n!+1$ composite?

I am trying to prove that if $n$ is composite then $n!+1$ is also composite. But I can't. Please help. If it is false then please give the number.
0
votes
0answers
46 views

A different proof of the distributive law for gcd and lcm

I am reading through a textbook (Elements of Abstract Algebra by Clark), and one of the exercises is to show that $$ \operatorname{lcm}(a , \operatorname{gcd}(b,c)) = ...
1
vote
1answer
26 views

Expanding Base 2B representation of an integer

Consider an integer$L$ written in Base 2B which digits $$a_n a_{n-1} a_{n-2} ... a_1 B$$ Where $a_i$ are arbitrary constants such that $9 \le a_i < 2B$. I am attempting to prove that the square ...
-2
votes
2answers
313 views

Is this a solution for the problem: $\ a^3 + b^3 = c^3\ $ has no nonzero integer solutions?

Is this a solution for the problem: $\ a^3 + b^3 = c^3\ $ has no nonzero integer solutions? Suppose $\ a^3 + b^3 = c^3,\ a,b,c \in \mathbb Z^*,\ $then: $c^3 - b ^ 3 = (c - b)((c - b) ^ 2 + 3cb) = ...
3
votes
2answers
185 views

Help understanding number theory definition

In my elementary number theory class, we have the following definition which i'm just having trouble understanding what they mean: Definition: A complete system of residues modulo m is a set of ...
0
votes
1answer
118 views

Primes and the number of digits of the prime [duplicate]

Say $n$ has $k$ decimal digits, all of which are ones. How would you show that if $n$ is prime, then $k$ is prime?
0
votes
1answer
153 views

Let $x = 2441921$. Factor $x$ into a product of primes.

Let $x = 2441921$. Factor $x$ into a product of primes. I found that: $1519^2 −x=−134560= −2^5 ·5 · 29^2$ and $1541^2 −x=−67240= −2^3 · 5 · 41^2$. I am trying to figure out what to do from here. ...
0
votes
2answers
70 views

Represent a prime number $p$ congruent to $1$ $\pmod{3}$ by a sum of a square and $3$ times a square

I want to have a proof of the fact that each prime number is the sum of a square and three times a square (Euler). Context I read the answer to my former question about the number of points on an ...
1
vote
4answers
72 views

$p$ prime, $p\mid a^k \Rightarrow p^k\mid a^k$

Suppose $p$ is a prime and $a$ and $k$ are positive integers. Prove that if $pa^k$ then $p^k\mid a^k$. I have already proven that if $a,b,n\in\mathbb{N}$ and if $a^n\mid b^n$, then $a\mid b$. I tried ...
1
vote
1answer
49 views

a square in a finite field of odd order

GF(q) is a finite field of order q, where q is odd. Prove that $a\in GF(q), a\neq0$ has a root in $GF(q)$ iff $a^{(q-1)/2}=1$. I tried to prove it this way: Suppose a has a root in ...
3
votes
3answers
115 views

Does $x^2+x+1 \equiv 0 \pmod {997}$ have solutions? Why or why not?

I'm have difficulty solving this problem in my textbook. Does $x^2+x+1 \equiv 0\pmod{997}$ have solutions? Why or why not? I guess the first step would be $$ \begin{array}{l} (2x+1)^2 \equiv ...
4
votes
0answers
46 views

Computing question: A quadratic which gives primes [closed]

This is about Project Euler Problem 27. The question is: Considering quadratics of the form $n^2 + an + b$, where $\lvert a \rvert < 1000$ and $\lvert b \rvert < 1000$ Find the product ...
3
votes
2answers
55 views

Prove that every non-prime natural number $ > 1$ can be written in the form of $n+(n+2)+(n+4)+…+(n+2m) = p$

I'm trying to prove that every non-prime natural number greater than $1$ can is equal to a sum of consecutive even or odd numbers. This can be resumed in : « $p,m,n \in ℕ$» , «$p > 1$» , «$n > ...
0
votes
2answers
38 views

Let $p$ be an odd prime and $(a,p)=1$. Show that $x^2≡a$ (mod $p)$ has solutions, then $x^2≡a$ (mod $p^n)$ always has solution , for any $n>1$.

Let $p$ be an odd prime and $(a,p)=1$. Show that $x^2≡a$ (mod $p)$ has solutions, then $x^2≡a$ (mod $p^n)$ always has solution , for any $n>1$. I have solved the first part but second part need ...
0
votes
2answers
54 views

Let $p > 3$ be a prime number. Show that $x^2 \equiv −3\mod p$ is solvable iff $p\equiv 1\mod 6$.

Let $p > 3$ be a prime number. Show that $x^2 \equiv −3\mod p$ is solvable iff $p\equiv 1\mod 6$. My try is let $a$ be a solution of $x^2 \equiv -3 \mod p$. so $a^{p-1} \equiv 1\mod p$. This ...
2
votes
1answer
55 views

Quadratic congruence with composite; $ x^2\equiv\ 31\ ({\rm mod}\ 11^4)$

This is an exercise in Burton I want to know the existence of shorter solution : Solve $$ x^2\equiv 31\ (11^4)$$ Note that we have a algorithm (or program) : If $$ x_k^2\equiv a\ (p^k)$$ then $$ ...
2
votes
1answer
44 views

Primitive roots and quadratic nonresidues modulo a prime of form $2^n+1$ [duplicate]

Let $p$ be a prime number. We call a unit $a$ in $\Bbb Z/p\Bbb Z$ a primitive root, if $\text{ord}_p(a)=p-1$. Any unit in $\Bbb Z/p\Bbb Z$ can be written as some power as some power of $a$. if $p$ is ...
1
vote
1answer
20 views

Exercise of Quadratic Reciprocity

This is an exercise in Burton : Prove that $$(5/p) =1\ iff\ p\equiv 1,\ 9,\ 11,\ or\ 19\ (20) $$ Note that $5=4+1$ so that $(5/p)=(p/5)$. In further $$ (p/5)^2=(5/p)(p/5) = (-1)^{1\cdot ...
4
votes
2answers
77 views

Binomial Congruence Modulo a Prime

Let $p$ be a prime and $a, b$ natural numbers such that $1 \leq b \leq a$. I am trying to prove that $$\binom{ap}{bp} \equiv \binom{a}{b} \pmod p.$$ Furthermore, I have been tasked with proving that a ...
0
votes
0answers
29 views

Find a criterion for the primes p such that (5/p) = 1. [duplicate]

Find a criterion for the primes p such that (5/p) = 1. I don't understand this question it is like Determine all primes P such that (5/p)=1 I appreciate any help
0
votes
2answers
43 views

Quadratic Residues in $\mathbb{Z}/3^n \mathbb{Z} $

I was playing around with quadratic residues in $3^n$ modulo systems and am now wondering if there is a neat closed form solution for the set of all quadratic residues in $\mathbb{Z}/3^n \mathbb{Z} $ ...
1
vote
3answers
103 views

Number theory proofs regarding gcd's

How would you prove if $ad-bc = 1$, then $(a+c,b+d)=1$
2
votes
3answers
148 views

Diophantine equation $ax + by = c$ has an integer solution $x_0, y_0$ if and only if $\gcd(a,b)|c$

Let $a,b,c$ be positive integers. Verify that Diophantine equation $ax + by = c$ has integer solution $x_0, y_0$ if and only if $GCD(a,b)|c$. Attempt Diophantine $ax + by = c$ has integer solution ...
4
votes
0answers
90 views

Adding Numbers Pattern

A few nights ago I couldn't sleep and so started doing this: I would take a number and add up all of its digits to get a new number and then add up all of those digits and so on until there was only ...
3
votes
2answers
34 views

Middle binomial coefficient mod 4

It is known that the middle binomial coefficient is always even. Show that $\binom{2n}{n}= 2 \mod 4$ if and only if $n$ is a power of 2.
1
vote
0answers
39 views

Which basis orders [for the natural numbers] have been proven?

The set $A$ of nonnegative integers is called an additive basis of order $h$ if every nonnegative integer can be written as the sum of $h$ not necessarily distinct elements of $A$. For example, the ...
2
votes
3answers
74 views

A general equation for Pythagorean triples of rational numbers

This question was asked by a friend of mine and I have no idea how to proceed. I am looking for a general solution for the equation $p^2+q^2=r^2$ where $p,q,r$ are rational numbers. PS: I am not ...
14
votes
1answer
217 views

How prove $\sqrt{r^2+c^2}$ is irrational

Question: Let $a,b,c$ are integer numbers,and $r$ real numbers, and $$ar^2+br+c=0,ac\neq 0$$ show that $$\sqrt{r^2+c^2}$$ is irrational. My idea: Note that, ...
3
votes
2answers
469 views

The sum of two irrational square roots

This is very similar to this question, but I was wondering if there was a simpler proof. In particular, a proof that would prove that $\sqrt{x}+\sqrt{y}$ is an irrational number if both $\sqrt{x}$ ...
1
vote
0answers
65 views

The sum (or difference) of two irrational numbers

So far I that for any irrational number without a real part (that $-n=\overline{n}$) plus/minus any irrational number with the same restrictions equals another irrational number. However, I want to ...
0
votes
1answer
27 views

Divisibility of $a^p-r$ and $a^q-r$ by the primes $p,q$

Let $p, q$ be prime and $a$ some positive integer such that $a = pq + r$ where $r$ is the remainder. Show that $p \mid a^p – r$ and $q \mid a^q – r$. Example: $p = 3$ and $q = 5$, $a = 17$ and $r = ...
-2
votes
1answer
56 views

Infinitely many rational and irrational numbers between two real numbers

Prove that there are infinitely many rational and irrational numbers between any two real numbers. I understand any number of rational numbers and irrational numbers can be inserted between any two ...
0
votes
1answer
26 views

Find a order 6 modulo 43

Note that $$ A = \{ 1,\ 2,\ \cdots,\ 42\} $$ Let $ A_6 = \{ a\in A|\ a$ has order $6 \}$ (Note that $2=\phi(6) = |A_6| $) To find $A_6$ we use the following fact : $ 3$ is a primitive root. Since $ ...
4
votes
2answers
109 views

How to prove $x^2-34y^2=17$ has no integer solutions?

My question is how might it be shown that the equation $x^2-34y^2=17$ has no solutions where $x$ and $y$ are both integers? I used this website to check whether there were solutions: ...
1
vote
1answer
117 views

Andrica's conjecture implies Bertrand's Postulate?

Let $p_n$ denote the $n$th prime. Recall Andrica's conjecture, which states that $$\sqrt{p_{n+1}}-\sqrt{p_n}<1\quad\text{ for all }\,n.$$ I think Andrica's conjecture implies Bertrand's postulate. ...
1
vote
1answer
48 views

Shortest way finding a primitive root of $15$

Note that Euler phi function $\phi(15)=8$. Note that $\{ 2,\ 4,\ 7,\ 8,\ 11,\ 13,\ 14 \}$ is the set of relative numbers to $ 15$. And $$ 2^4\equiv 1\ (15)$$ so that since $4<\phi(15)$, $2$ is not ...
2
votes
2answers
85 views

Divisibility for 7

I have seen other criteria for divisibility by 7. Criterion described below present in the book Handbook of Mathematics for IN Bronshtein (p. 323) is interesting, but could not prove it. Let $n = ...
1
vote
1answer
40 views

Can $3q^2-1=m^2$ be not a perfect square

Prove that $3q^2-1=m^2$ is not a perfect square. It is posing little confusion as the right hand side is already a perfect square
1
vote
3answers
61 views

Even number being express as $4q$ or $4q+2$

Prove that every positive even integer $n$ can be expressed as $n=4q$ or $n=4q+2$, $\forall q\in Z$. I expressed $n$ as $n=4q+r$ using Euclid's lemma and I have been able to prove that $n=4q+0, ...
3
votes
3answers
97 views

Product of two negative numbers is positive [duplicate]

What is the practical proof for $-1(-1)=+1$. Actually multiplication is repetitive addition. I am struggling how can I provide an activity to prove practically $-1(-1)=+1$
3
votes
1answer
62 views

If $p$ is prime, prove that $\exists k\in\lbrace 5,-7,9,-11,..\rbrace$ in $(\mathbb{Z}/p\mathbb{Z})^*$ so that the Legendre symbol $(\frac{k}{p})=-1$

The BSPW primality test, when given $p$ as input, iterates over $k \in \lbrace 5,-7,9,-11,...\rbrace$ as long as the Legendre symbol $(\frac{k}{p})=1$. If $(\frac{k}{p})=0$, it returns "composite". So ...
0
votes
0answers
40 views

A question related to the Descartes-Frenicle-Sorli conjecture on odd perfect numbers

Good day to everyone! I apologize in advance for the somewhat long post, but I had to put in all the details into a single question to communicate what I believe to be a viable approach to odd ...
3
votes
4answers
147 views

Find all $n$ for which $2^n \ge (n+1)^2$

Find all of the elements of $X= \{ n \in \mathbb N: 2^n \ge (n+1)^2\}$ Could someone give me a hint to nudge me in the right direction?
1
vote
0answers
29 views

Lowest sum of 2 sets of number pairs

I am given a set of unique integers $n$. I need to compute the smallest sum $s$ such that there are two different pairs of integers $(x1, x2)$ and $(y1, y2)$ where $x1 < x2$ and $y1 < y2$ and ...