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.

4
votes
1answer
36 views

Proving numerator of sum is divisible by prime p

Let $p$ be an odd prime. For each integer $a$, set $$S_a=\sum_{k=1}^{p-1}\frac{a^k}{k} .$$ Write $S_4+S_3-3S_2$ in the form $$S_4+S_3-3S_2=\frac{m}{n}$$ where $n,m\in\mathbb Z$ satisfy $\...
1
vote
2answers
44 views

What are the possible solutions for the diophantine equation $4x^2-3y^2=1$ and is there a general formula?

Assuming that $a = x^2$ and $b = y^2$, i converted this equation to a linear diophantine equation for sake of convenience: $$4a - 3b = 1$$ where after calculating a particular solution (like $(1, 1)$...
1
vote
1answer
33 views

Find the $\gcd(x^m+ a^m,x^n+a^n) $

I really need help with this problem. I think I should take first $d=\gcd(m,n)$ But I don't know how to use this fact. I would really appreciate some help
0
votes
0answers
49 views

Find all possible primes $p$ and $q$ such that $3p^{q-1}+1$ divides $11^p+17^p$.

Find all possible primes $p$ and $q$ such that $3p^{q-1}+1$ divides $11^p+17^p$. Please help me to solve this. Firstly I proceed with odd and even primes but I got no result. Please solve this.
1
vote
4answers
47 views

In diophantine $3b^2=a^2$ where $a$ and $b$ are coprime, does $3|a$?

Integers $a$ and $b$ are co-prime and $3\cdot b^2=a^2$. $3\cdot b^2=a^2$, implies $a^2$ is divisible by 3 since, $3b^2$ is divisible by 3. Is $a$ divisible by 3?
1
vote
2answers
44 views

How Wilson's theorem implies the existence of an infinitude of composite numbers of the form $n! + 1$?

This is a paragraph in David M. Burton, "elementary number theory, seventh edition: ": But I do not understand: 1- How Wilson's theorem implies the existence of an infinitude of composite numbers ...
1
vote
0answers
30 views

Norms, Orders, and 'almost' valuations in Number Fields

This is one of those questions that feels true, but I can't prove or disprove it. Let $K = \mathbb{Q}(\sqrt{D})$, where $D < 0$ is squarefree, and let $k>0$ be some positive integer. If you ...
2
votes
2answers
76 views

How many tuples of {$a, b, c, …$} satisfy $abc… \leq n$?

Let $n$ and $k$ be positive integers. Let $a, b, c, ...$ be $k$ positive integers such that $abc... \leq n$. How many tuples of {$a, b, c, ...$} satisfy the inequality? Note that the tuples {$a=1, ...
1
vote
1answer
60 views

$\,m = {\rm lcm}(a,b)\iff a,b\mid m\ \, \& \ \gcd(m/a,m/b)=1$

For $a \in\Bbb N$, $b\in\Bbb N$, $μ \in\Bbb N^*$, we have $μ = \operatorname{lcm}(a,b) \iff μ = αa\text{ and }μ= βb$ and $\gcd(α,β)$ is $1$ Till now I succeeded to prove the left $\Rightarrow$ ...
0
votes
0answers
38 views

largest known twin semiprimes and consecutive semiprimes

What are the largest known semiprimes differing by 2? What is the largest known pair of consecutive numbers that are both semiprimes? Has anyone computed this?
1
vote
2answers
55 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$.
0
votes
2answers
38 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 ...
2
votes
1answer
55 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
31 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 ?...
4
votes
2answers
65 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 algebraic number field $K$, $\alpha \...
0
votes
2answers
29 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
39 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
38 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
41 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
35 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 ...
2
votes
0answers
63 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
49 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
2answers
97 views

A Complete Proof of the Fundamental Theorem of Arithmetic?

UPDATE I posted an answer but it appears I have a ways to go. In this update to my question I changed the title from $\quad$ A Simple Proof of the FTA using only elementary theory? to the one ...
1
vote
1answer
57 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
31 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
54 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
53 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
47 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
30 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
30 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
73 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.
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
81 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
27 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
42 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
42 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
51 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
100 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
74 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$ [closed]

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 ...