Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [elementary-number-theory]

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

0
votes
2answers
41 views

Hi, so my idea is to probably factorize that expression and use this to prove. I am still stuck however. [on hold]

Prove that if $a$ and $b$ are two odd primes, then $a b+b-a-a^{2}$ is a multiple of $4$.
-2
votes
0answers
22 views

Shifting quadratic residues

Let $p\equiv 3\pmod 4$ and $G$ be the set of nonzero quadratic residues modulo $p$ (so $G=(p-1)/2$). For $1\leq a\leq p-1$, let $G_a=\{(a+g)\pmod p\mid g\in G\}$. What is the size of $G_0\cap G_a$? I ...
0
votes
2answers
34 views

Do such unique representations of positive integers exist?

It is well known that every positive integer $n>0$ can be represented uniquely in the form $$ n=2^k(2m+1), $$ for positive integers $k,m\geq0$. Does there exist one or more constants $c>1$ such ...
0
votes
0answers
38 views

Find the condition on $p$ such that equation $x^2+3 \equiv 0 \pmod{4p^2}$ has roots

Problem: Find the condition on $p$ such that equation $x^2+3 \equiv 0 \mod 4p^2$ has roots with $p$ is a prime and find the number of roots of this equation. My solution: $x^2+3 \equiv 0 \mod 4p^2 \...
0
votes
0answers
29 views

An elaboration of a part in the proof of a criterion for finding Carmichael numbers.

The criteria and its proof is given below: But I do not understand why $p_{i} - 1|n-1$ implies $p_{i} | a^{n-1} - 1$ if we know that $p_{i} | a^{p_{i}-1} -1$. could anyone explain this for me please ?...
3
votes
1answer
43 views

Ring of Integers for $\mathbb{Z}[\sqrt{d}]$

I'm pretty sure this is a very basic thing, but my background is in physics and I have never previously done any number theory. We have as a theorem that for an algberaic number field $K$, $\alpha \...
0
votes
2answers
26 views

A discrepancy in understanding the proof that any Carmichael number is square free.

The proof as given in " David M. Burton " is as follows: Suppose that $a^n \equiv a \pmod n$ for every integer a, but $k^2\mid n$ for some $k > 1.$ If we let $a = k,$ then $k^{n} \equiv k \pmod n.$...
0
votes
4answers
36 views

A discrepancy in the proof that 561 is Carmichael number.

The proof is given below: But I do not understand the statement in the line before last which says "These give rise to the single congruence $a ^{560} \equiv 1 \pmod n$ where gcd(a, 561) = 1 ", I do ...
1
vote
1answer
36 views

Easy number theory/proof by induction

This is my attempt to solve the following question: "Use induction to show that if $(a,b)=1$ (greatest common divisor of $a$ and $b$), then $(a,b^n)=1$ for all $n\geq 1$." We have that $(a,b)=1$, ...
1
vote
1answer
40 views

Irreducible polynomials for that each output is divisible by an integer n

Feel free to delete this question if it has been asked somewhere else before. I've recently stumbled upon this question on the Mathematics StackExchange and I've wondered how the polynomials for ...
1
vote
0answers
34 views

Index of Fibonacci primes and Lucas primes.

For an integer $n\geq 0$ let $F_n$ denote the $n$th Fibonacci number and let $L_n$ denote the $n$th Lucas number. It is known that $F_n$ is prime only if $n$ is prime or $n=4$. According to ...
1
vote
0answers
52 views

Efficient method to check whether the nearest prime has distance $d$ or more?

Suppose, a prime $\ p\ $ is given. How can I check efficiently whether the distance to the nearest prime is $\ d\ $ or more , if $\ d\ $ is given ? My approach is to start with $\ c=2\ $ and as ...
1
vote
0answers
36 views

Pythagorean Quadruples and Stereographic Projection

I am trying to solve Diophantine equation $a^2+b^2+c^2=d^2$ by transforming this equation, assuming $d \neq 0$, into a sphere $ (\frac{a}{d})^2 + (\frac{b}{d})^2 +(\frac{c}{d})^2 = x^2 + y^2 +z^2 =1$ ...
0
votes
1answer
77 views

A Simple Proof of the FTA using only elementary theory?

By elementary theory, we mean avoiding as much number theory as possible. The exposition below is sketchy but the necessary details involve 'primitive' constructions, like using the fact that the ...
1
vote
1answer
49 views

Product of binomial coefficients and interesting properties

I recently encounter the following quantity \begin{eqnarray} \frac{n^+!n^-!}{n!}\frac{k!}{k^+!k^-!}\frac{l!}{l^+!l^-!} \end{eqnarray} $n^\pm,n,k^\pm,k,l^\pm,l$ are all non-negative integers. There ...
-1
votes
0answers
30 views

necessary and sufficient conditions that a number being prime or prime of special form? [on hold]

I like to gather some statements about the properties of prime numbers or prime of the specific forms. For instance 1) A prime number is a whole number greater than 1 whose only factors are 1 and ...
3
votes
1answer
52 views

Can the minimum of two consecutive prime gaps become arbitary large?

Here : https://oeis.org/A023186 the so-called "Lonely primes" are shown. Let $$[a,b,c]$$ be a triple of consecutive primes and define $$d:=\min(c-b,b-a)$$ My question : Can we prove that $d$ ...
1
vote
1answer
51 views

Continued fractions with every element 1 or 2

Let's say we have continued fractions of irrational numbers of the form $$ [a_0, a_1, a_2,...]: a_0 \in \mathbb{Z}, a_i \in \{1,2\}. $$ Is there any way to determine a number, say $x\in [0,1],$ that ...
0
votes
2answers
46 views

When can a number be expressed as the sum of two squares?

I'v learnt from this site that a composite number $n$ can be expressed as the sum of two squares if and only if its prime factor do not contain a prime $p \equiv3 \pmod 4$ which is powered to even ...
2
votes
1answer
28 views

Solution to equation modulo p

Under the assumptions that $$p\cong 1 \mod 5$$ and $$g = 2(c+c^{-1})+1$$ where $c$ has order $5$ modulo $p$. I need to show that $g^2 \cong 5 \mod p$. I have that $$g^2=4(c^4+c^3+c^2+c)+9$$ I know ...
1
vote
1answer
29 views

How many integers between 2001 and 3000 inclusive are not divisible by any of the three prime numbers 3, 7 and 13?

I approached by finding the number of integers between 1 and 3000 inclusive and the number of integers between 1 and 2000 inclusive, finding the difference between these and subtracting it from 1000 (...
1
vote
0answers
72 views

Primes that divide integers of the form $n^2+1$ or $n^2+3$ [on hold]

A similar question is supposedly included in an open assignment so I have retracted my working.
1
vote
0answers
38 views

Is the average deviation of a composite number unique?

Let $s_n$ be the standard deviation of the divisors of the natural number $n > 1$ then, $\dfrac{s_n}{n}$ is injective over composites. In other words, there does not exist composite numbers $m$ ...
0
votes
2answers
15 views

Seed solutions to a diophantine equation and Reversibility of the Conway's topograph method

I came across the answer to solving a quadratic diophantine equation on this site by @Willjagy: General method for determining if $Ax^2 + Bx + C$ is square I wish to know how the four seed solutions ...
1
vote
2answers
55 views

Which intuitive idea is captured by the definition of the successor of a natural number in terms of union : $S(n) = n \cup \{n\}$

Maybe an answer to this question is that we want the successor to have " one more " element than the prececessor. Is this explanation correct? An objection I see is that the explanation is not ...
1
vote
3answers
80 views

Elementary demonstration; $p$ prime, $1 \lt a \lt p$, $\;1 \lt b \lt p \quad$ Then $ p\nmid a b$

Update: Using Bill Dubuque's lemma and logic proving Euclid's lemma, we can supply an elementary proof. To get a contradiction, assume than $p \mid a b$. Let $S = \{n \in \Bbb N \, | \, p \mid nb \}$...
1
vote
0answers
26 views

Solution to an indeterminate equation

I have an equation of the form $$Dx^2-2s.t.x+t^2=c^2$$ where $s$, $t$ and $x$ are positive integers and $c$ can be any positive and odd integer. Is there a method to recursively find the values of $x$ ...
-4
votes
2answers
40 views

Show that $a^4(b^2-c^2) + b^4(c^2-a^2)+c^4(a^2-b^2)$ is divisible by $(a+b)(b+c)(c+a)(a-b)(b-c)(c-a)$. [on hold]

Show that $$a^4(b^2-c^2) + b^4(c^2-a^2)+c^4(a^2-b^2)$$ is divisible by $$(a+b)(b+c)(c+a)(a-b)(b-c)(c-a).$$
0
votes
3answers
41 views

prove that a number N is divisible by $5^k$ if the last k digits are divisible by $5^k$. [on hold]

prove that a number $N$ is divisible by $5^k$ if the last $k$ digits are divisible by $5^k$.
1
vote
2answers
53 views

Elegant Proof that $m | xn \implies \frac{m}{(m,n)} | x$ [duplicate]

I have a proof that shows $m | xn \implies \frac{m}{(m,n)} | x$ which leans heavily on prime factorizations. Is there a more straightforward proof? Edit With this question, I was looking for a proof ...
2
votes
2answers
33 views

Show that the relation $(- 1) (- 1) = 1$ is a consequence of the distributive law [duplicate]

Show that the relation $(- 1) (- 1) = 1$ is a consequence of the distributive law. This question is the first problem from 'Number Theory for Beginners" by Andre Weil. I cannot get the point from ...
1
vote
2answers
49 views

For given $ab\leq n$, do there exist $a'\geq a$ and $b'\geq b$ such that $a'b'=n$?

For example, given $a=3$, $b=3$, and $n=14$, no such $a',b'$ exists. On the other hand, for $a=3$, $b=3$, and $n=12$, we can use $a'=3$ and $b'=4$. Is there a simple formula that can help determine ...
2
votes
2answers
63 views

Remainder of $(1\cdot2\cdots102)^3$ modulo $105?$

I am having trouble in finding the remainder of $(1\cdot2\cdots102)^3\mod 105$ It is not possible to apply Wilson's Theorem here because 105 is composite. Can anybody help me?
0
votes
1answer
28 views

A different statement of the Chinese remainder theorem.

My professor gave us a statement for the "Chinese Remainder Theorem" different from that stated in David M. Burton, which say: If $n_1,\dots,n_k$ are coprime positive integers, then there exist a ...
0
votes
1answer
41 views

If $p$ is a prime, and $2p = 2 \mod 4$ then $p = 3 mod 4$

If $p$ is a prime number, and $2p = 2 \mod 4$ then $p = 3\mod 4$ Is this true? I know that of the form $2x = 2\mod4$ then my solution must by of the form $2k+1$ or $1,3 \mod 4$ but does making p ...
0
votes
3answers
69 views

Solving a congruence, tricky implication

We want to prove that $$243x \equiv 1 \mod 2018 \implies x^{403} \equiv 3 \mod 2018$$ My try : Assume that $243x \equiv 1 \mod 2018$ We have $x^{2016} \equiv 1 \mod 2018$ (by Fermat ($1009$ is ...
1
vote
1answer
99 views

There cannot be more than three primes of the form $n^{n^2}-k$ for the same $k$?

I was searching for primes of the form $n^{n^2}-k$ on PARI/GP and noticed that primes of this form for same $k$ are quite rare. The probability of finding a prime of this form is $\frac {1}{n^2 \log (...
1
vote
1answer
54 views

$a^x + b^y = c^z \Rightarrow a^{x-2} + b^{y-2} = 0 $ (mod c) if $x,y,z > 2$ and $a,b,c$ are pairwise coprime?

Let $a,b,c,x,y,z$ be positive integers such that $x,y,z > 2$ and $a$,$b$,$c$ are pairwise coprime. Suppose it is given that $a^x + b^y = c^z$ (i.e $a^x + b^y \equiv 0 (\text{mod } c)$), then is it ...
1
vote
1answer
71 views

Prove that the sum $1+2+3+4+5+6+7+\ldots+n$ is never prime for $n>2$.

I'm trying to prove that the sum of consecutive integers $1+2+3+4+5+6+\ldots+n$ is never prime for all integers $n>2$. Here's what I tried. I assumed that the sum $1+2+3+4+5+\ldots+n=p$, where $p$ ...
0
votes
1answer
36 views

Proof that any integer $z>1$ can be written as $2x+y$, where $x>y$

Imagine a multiple choice questionnaire with 3 choices $a, b,$ and $c$. At the end the sums of each choice are tallied. It seems it's always possible to have a tie for first, as long as the total ...
-1
votes
1answer
31 views

Greatest Integer Function - solve for real $x$ [on hold]

Solve for real $x$: $[x^2]=[2x-1]$ where $[x]$ is floor/box function.
1
vote
2answers
37 views

Prove that there exists an integer greater than x such that any polynomial $f(x)$ will be strictly non-negative and get large?

Hi I am taking a number theory class and so far I have been proving modular congruences, modular arithmetic, and prime properties. There is this theorem that came up in the textbook and apparently it ...
2
votes
1answer
70 views

What is the difference between, a “square” and a “perfect-square”, number?

Is, "36", a perfect square? I know that, "4" is a perfect square. Similarly, "1","9","25", are "perfect-square"s.
0
votes
0answers
166 views

Does no prime exist of the form of $k^k+11$? [on hold]

I tried searching for primes of the form $k^k+11$ on PARI/GP and found that no such prime exists for $k \le 10^4$. Questions: $(1)$ Is there any reason I cannot find a prime of the form $k^k+11$? ...
-1
votes
0answers
17 views

Infinitely many $n$ such that $2^n$ ends with $n$ [duplicate]

Prove that there are infinitely many integers $n$ such that the decimal representation of $2^n$ ends with $n$.
2
votes
1answer
90 views

Infinitude of super happy primes

Similar to happy primes, I define super happy primes by the following process: $(1)$ Find the sum of the digits raised to the power of themselves. Ex. $13$ gives sum $ = 1^1 + 3^3 = 28$ $(2)$ If ...
0
votes
0answers
17 views

A discrepancy in the used general solution of linear diophantine equation in David M. Burton book.

In David Burton book "seventh edition", the general solution of linear diophantine equation is given below (in page 34): Then in page 76 after linking linear congruences with linear diophantine ...
2
votes
1answer
14 views

A difference in a formula of theorem 4.2(e) on congruence relations.

The statement of the theorem said : If $a \equiv b \pmod n$ then $ac \equiv bc \pmod n$. But I have seen it in other place as: $a \equiv b \pmod n$ then $ac \equiv bc \pmod {nc}$. Are they ...
0
votes
1answer
29 views

For every $n\in\mathbb{N}$ , the equation $\varphi(x)=n$ has a finite number of solutions [duplicate]

How can I prove that for every $n\in\mathbb{N}$ , the equation $\varphi(x)=n$ has a finite number of solutions ? $\varphi(n)$ denotes the totient function.
5
votes
1answer
62 views

Is there a maximum number of consecutive sexy prime pair sums that are all divisible by $10$?

I was finding the sums of pairs of sexy primes (prime numbers that differ by 6) and noticed that there are a lot of pairs who's sum is divisible by $10$. Ex. $(7, 13)$ as $7+13=20$ and $20$ is ...