Questions tagged [elementary-number-theory]

Questions on divisibility, gcd and lcm, congruences, linear Diophantine equations, Fermat's and Wilson's theorems, the Chinese Remainder theorem, primitive roots, quadratic congruences, quadratic number fields and other related topics which may be treated in first courses on number theory. More advanced topics should instead use the number-theory or other tags.

Filter by
Sorted by
Tagged with
0
votes
1answer
20 views

Prove that the number of primes that divide $B=\left \{ \sum_{i=1}^n b_ia_i^n : n\in \mathbb{N} \right\}$ is infinite

I got this interesting question which says Let $n\geq 2$ and let $a_1,a_2,\dots ,a_n$ be positive integers (not necessarily distinct) such that $(a_1,a_2,\dots ,a_n)=1$ (where $()$ represents G.C.D.) ...
4
votes
0answers
67 views

When is $14k^4 - 6k^2 + 1$ a perfect square?

Is there some sophisticated method (or maybe some easy one, though I doubt it) to show that the only solution to $m^2 = 14k^4 - 6k^2 + 1$ in positive integers is $k=1$, $m=3$? Perhaps something around ...
0
votes
0answers
14 views

Do these modifications of Pillai's conjecture equation still have (in)finitely many solutions?

So I'm aware of the Pillai's conjecture that says that $Ax^n-By^m=C$ has only finitely many solutions $(x,y,m,n)$ if $(m,n)\neq (1,1)$, when $A,B,C$ are fixed positive integers. I have the following ...
0
votes
0answers
40 views

For which $n$ there exists such an $m$?

The question is that: For which positive integer $n \geq 2$,there exists an integer $m$ such that $m^2$ is an n-digit number consisting of all the integers from $0$ to $n-1$ when presented in base $n$...
1
vote
0answers
44 views

Efficiency of paper and pencil division

I am trying to understand why the second paragraph under the stated division algorithm seems to mention the verification of one of the values for $q_i$ takes $O(l)$ time, while I think it would take $...
3
votes
2answers
30 views

divisibility remains by scaling multiplicative order [duplicate]

I want to show that if p | $a^{e}-1$ then also p | $a^{ek}-1$ where k is any integer. Def. of order in terms of divisibility: Let $m ≥ 2$ and a be any integer coprime to $m$. The order of $a$ mod $m$ ...
0
votes
1answer
36 views

Can a logarithm to a fractional base have an integral result?

Consider the following setup. Let $b > 1$ be a fractional base, i.e. $b \in \mathbb{Q} \setminus \mathbb{N}$. My question is whether there could potentially exist an $x \in \mathbb{N}$ such that $\...
0
votes
2answers
29 views

How to figure out all possible pairs of numbers with a HCF?

The product of two numbers is $13005$ and their HCF is $17$. Find all possible pairs of numbers. I've done the first part of the question but I'm stuck on how to find all possible pairs of numbers. Is ...
0
votes
0answers
24 views

What would the answer be? [duplicate]

Both numbers are above $8,$ their HCF is $8$ and their LCM is $80.$ Find the two possible numbers. I'm very stuck on this question and was wondering if there was an easy way to answer it
0
votes
0answers
24 views

Do we have that $x$ divides $cb$ with $x,b,c\in \mathbb{Z}$ implies $\gcd(x,b)>1$ [duplicate]

I am trying to prove that the set of zero divisors of the ring $\mathbb{Z}/_{b\mathbb{Z}} $ is equal to $\{[x] \in \mathbb{Z}/_{b\mathbb{Z}}: \gcd(x,b)>1\}$. Therefore I started with the set of ...
2
votes
0answers
38 views

Maximum value of $\text{lcm}(n_1,n_2,…,n_k)$ given $n_1+…+n_k=X$

Find the maximum value of $\text{lcm}(n_1,n_2,...,n_k)$ given $n_1+...+n_k=X\in\mathbb{Z^+}$,where $n_1,...,n_k$ and $k$ are to be determined. I came across this as a lemma while solving a group ...
5
votes
2answers
72 views

An interesting identity regarding partitions of $m$ into powers of two

This question appeared in an exam I was giving- Suppose we have $n$ balls and we place them in a sequence of bins as follows. At least one ball is put into the first bin, and each successive bin has ...
4
votes
3answers
84 views

Comparing numbers of the form $c+\sqrt{b}$ (eg, $3+3\sqrt{3}$ and $4+2\sqrt{5}$) without a calculator

It is easy to compare to numbers of the form $a\sqrt{b}$, simply by comparing their squares, for example $3\sqrt{3}$ and $2\sqrt{5}$. But what if we have $a=3+3\sqrt{3}$ and $b=4+2\sqrt{5}$ for ...
1
vote
1answer
64 views

A Number Theoretic Game

I got this question in an exam I was giving- Alice and Bob are playing a game. There are $n$ coins laid out on a circular table, at positions marked from $1$ to $n$. In each round, Alice picks a list ...
4
votes
0answers
64 views

If t is a quadratic residue mod p, how can I efficiently solve the equation $x^2=t \pmod {p}$? [duplicate]

I know that if $({t\over p})=1$, then $t$ is a quadratic residue, which means that $x^2 \equiv t$ mod p has solutions. So is there any skills or methods that I can use to solve the equation given a ...
5
votes
1answer
100 views

A Fibonacci conjecture: $\sum_{j=1}^n(\sum_{k=1}^jF_k^2)^3=\left(\sum_{j=1}^nF_j\left(\sum_{k=1}^j F_k^2\right)\right)^2$

I have been staring at the identity below for over a year now but I haven't found a way around proving it even though I have tested for $n \le 2000$ using my computer. $$\sum_{j=1}^{n} \left(\sum_{k=...
5
votes
2answers
84 views

Are there an infinite number of integers $n$ such that $(3n)(n+1)$ is a perfect square?

I am looking for cases in which $\sqrt{3n(n+1)}$ is an integer, i.e. cases in which $$ 3n(n+1)=m^2,\quad m\in\mathbb{N}. $$ I can find solutions such as $$ n=0,3,48,675,9408,131043,\dots $$ and I ...
4
votes
5answers
160 views

Number of integer solutions of $a^2+b^2=10c^2$

Find the number of integer solutions of the equation $a^2+b^2=10c^2$. I can only get by inspection that $a=3m, b=m,c=m$ satisfies for any $m \in Z$. Is there a formal logic to find all possible ...
0
votes
1answer
66 views

If $p$ divides $x^4 + x^3 + x^2 + x + 1$ and $x \equiv -1 \mod{5}$, then $p \equiv 1 \mod{5}$

I know that $x^5 - 1 = (x-1)(x^4 + x^3 + x + 1)$. So if $p$ divides $x-1$, then $p$ divides $x^5 - 1$. But I'm not sure how to proceed from here. I've tried looking at residues mod $p$ and mod 5, but ...
3
votes
2answers
76 views

A discussion about exponential diophantine equations and pythagorean triples

Do all pythagorean triples $(a,b,c)$ have the identity that the three (exponential diophantine) equations \begin{equation} a^x+b^y=c^z \end{equation} \begin{equation} b^y+c^z=a^x \end{equation} \...
0
votes
0answers
11 views

Showing that any composite Fermat number is a strong pseudoprime wrt base 2

For $m \geq 0$, the $m$-th Fermat number is defined by $F_m = 2^{2^m}+1$. If $F_m$ is a strong pseudoprime wrt base $2$, then by definition, there must exist some $0 \leq i < 2^m$ such that $2^{2^i}...
4
votes
1answer
80 views

Prove that $f(n)=n$, $\forall n \in \mathbb N$ for the strictly increasing multiplicative function [duplicate]

Problem Let $f : \mathbb{N}\to\mathbb{N}$ be a strictly increasing function such that $f(2) = 2$ and $f(mn) = f(m) \cdot f(n)$ for every relatively prime pair of positive integers $m$ and $n$. Prove ...
0
votes
0answers
35 views

Showing that if $m \leq 2^n-1$, then the $m$-th Fermat number divides $2^{F_n}-2$

The $m$-th Fermat number is defined by $F_m = 2^{2^m}+1$ (where $m\geq 0$ is an integer). The condition that we must show is equivalent to $2^{F_n} = 2^{2^{2^n}+1} \equiv 2$ modulo $F_m$. This also ...
0
votes
3answers
55 views

If $p,q$ are two primes with $p \neq q$, why does $p \not\equiv 1$ (mod $q-1$) or $q \not\equiv 1$ (mod $p-1$) hold?

I assume that $p \equiv 1$ (mod $q-1$), so I must show that this implies $q \not\equiv 1$ (mod $p-1$) then. The assumption implies that there is a $c$ such that $p-1 = c(q-1)$. In particular, since $c$...
0
votes
1answer
129 views

Questions about the sequence OEIS A059650

Comparing the sequences OEIS A001951 $$a(n) = \lfloor n\sqrt{2}\rfloor = \lfloor \sqrt{2n^2 }\rfloor = \lfloor \sqrt{2*Square }\rfloor:\quad \{0, 1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, .....
0
votes
4answers
64 views

Why does Euclid's lemma have the requirement of coprimes?

I was reading the general form of Euclid's lemma which states: If $a \mid bc$ and $a$ is relatively prime to $b$ then $a \mid c $ I don't really understand why the "relative prime" ...
0
votes
1answer
41 views

Testing membership for perfect square number

Is it sufficient to test that if a positive integer $n$ ends in $0, 1, 4, 5, 6, 9$, and that $n \equiv 0, 1 \bmod 4$ then $n$ is a perfect square? The numbers $0, 1, 4, 5, 6, 9$ I got from the ...
0
votes
1answer
51 views

Showing $\mathbb{Z}_p$ is a ring [duplicate]

In $\textit{A Classical Introduction to Modern Number Theory}$, the authors define $\mathbb{Z}_p$ as a set where $p$ is a prime number and $a,b$ form the rational number $a/b$ such that $p\nmid b$. ...
-4
votes
1answer
41 views

Prove the equation if $b$ is a prime [duplicate]

When $b$ is prime and $a>0$ is any integer: $$(1/a)\pmod b \equiv a^{b-2}\pmod b$$ Can somebody explain me how this equation holds true in number theory. Someone told me that it can be proven ...
3
votes
1answer
79 views

Number of Niven numbers less than or equal to n

Niven (or Harshad) numbers are known as the numbers that are divisible by the sum of their digits. The sequence of Niven numbers begins as $1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 18, 20, 21, 24, 27, 30, ...
0
votes
1answer
31 views

Number theory and Dirichlet's principle problem

Prove that there exists such a number, that can be divided by 2011 and ends with ...2010 Give me a hand, please. Unfortunately, i do not even know where to start.
2
votes
2answers
75 views

Find the number of drinking people (problem from 1544)

Reading about GCD and LCM I came around this problem (apparently dated from around 16th century): A group of 20 person which are men, women and children drink in a tavern. Together they spend 18 ...
0
votes
0answers
39 views

Prove that for every $n \in \mathbb{N}^*$ [closed]

Prove that for every $n \in \mathbb{N}^*$ $$ \sum\limits_{d\mid n} {\frac{n}{d} \cdot \sigma (d)} = \sum\limits_{d\mid n} {d \cdot \tau (d)} . $$
1
vote
2answers
47 views

Adding finite list of square roots of primes to $\mathbb{Q}$

I have that idea which I'm pretty sure that is true- but I haven't succeded to prove it: Given finite list of primes ${p_1,p_2,p_3,...,p_n}$ , and extension of the rational field with the square roots ...
12
votes
1answer
263 views

A problem about Prime Numbers and Perfect Squares

Can we find all $n$ such that there exists a prime number $p$ s.t. $1+p+p^2+\cdots+p^n$ is a perfect square, where $n$ is a natural number? For $n=1$, when $p=3$, $1+p=4$, which fits our standards. ...
-1
votes
1answer
54 views

Strange Number Base System's Name [closed]

Consider a base where there are six digits. The first digit denominates the base, and the other five marks the number proper. I was thinking of it working something like this (note that I will put the ...
2
votes
1answer
54 views

high order integer equation

Find all tuple $(x,y)$ such that $x,y$ are integers and $(x^2-y^2)^2=20y+1$. First i see that $x^2-y^2$ is odd and from the fact that a difference between square of two odd is multiple of $8$ and ...
-1
votes
0answers
44 views

A divisibility number theory problem

Prove: There exists a number $n$ which has $2021$ different prime divisors s.t. $n\mid 2^n+1$. My idea is to observe the number $2021$. First, $2021=43\times47$. Let $$n=\sum_{i=1}^{2021}p_i^{\...
6
votes
3answers
191 views

How many numbers are there such that its number of decimal digits equals to the number of its distinct prime factors?

Problem A positive integer is said to be balanced if the number of its decimal digits equals the number of its distinct prime factors. For instance, $15$ is balanced, while $49$ is not. How many ...
-1
votes
0answers
18 views

Is it true that the nth root of a rational number a/b, lowest terms, is rational iff a^(1/n) and b^(1/n) are integers? [duplicate]

I suppose it’s easy to prove. I mean a and b are such that gcd(a, b) = 1, where a and b are integers. I should clarify n is a positive integer.
1
vote
1answer
41 views

Is it true that all primes $n<p<2n, \; p<2n-1$ are members of odd Goldbach partitions of $2n+1$?

By Bertrand's Postulate, there is at least on prime $p$ such that $$n<p<2n, \quad n>1$$ The question is: Is it true that all primes $n<p<2n, \; p< 2n-1$ are members of odd Goldbach ...
0
votes
0answers
48 views

transition from multiplicative order to Fermat's little theorem [duplicate]

I am reading a paper and they write that Fermat derived his little theorem from this observation: If $p$ is a prime, and $a$ is any number not divisible by $p$, then the order of a modulo $p$ divides $...
3
votes
0answers
70 views

Problem books on algebraic number theory

I came across the book Basic number theory by André Weil. It mainly introduces concept of Adeles, classification of locally compact fields, adelic points in varieties and schemes in modern number ...
0
votes
0answers
40 views

$p$-adic valuation in $\mathbb{Q}$ existence

For a rational number $r \in \mathbb{Q}$, the claim is that we can write $$ r = p^{e}\cdot\frac{a}{b}, \,\,\, e,a,b \in \mathbb{Z}, b \neq 0 $$ with the properties that $\gcd(a,b)=1$ and $p$ does not ...
0
votes
0answers
36 views
0
votes
1answer
50 views

Proof: If a and m are coprime, then $a^{t}$ ≡ 1 (mod m) for some t, 1 ≤ t < m.

I have a question regarding this proof: If $a$ and $m$ are coprime, then $a^{t} ≡ 1 $ (mod m) for some t, $1 ≤ t < m$. Since $a$ and $m$ are coprime, $m$ does not divide as for any $s$, and so the $...
-2
votes
0answers
57 views

For the eqn. $ab +bc +ca = y^n$, where a,b,c are +ve consecutive numbers, there exists no integral solutions for y when n>1? [closed]

For the eqn. $ab +bc +ca = y^n$, where a,b,c are +ve consecutive numbers, there exists no integral solutions for $y$ when $n>1$.If we choose any one of $a,b,c$ as $0$ then we will have a square, ...
-3
votes
0answers
40 views

Help with data for Number of primes < n^2 [closed]

Has anyone computed the OEIS sequence A038107, i.e. Number of primes < n^2, up to 1 billion? If so, could you share the data with me please? Or simply the π(n), i.e. the number of primes not ...
1
vote
4answers
82 views

Find positive integer $x$ such that $3x+1=2^n$

Just by computing it seems $3x+1=2^n$ is true for every other $n$ such that 2^n: 16, 64,..., which corresponds to $x=5, 21,...$. This intuitively makes sense, after all, $3x+1$ is even every time $x$ ...
2
votes
2answers
88 views

For all m there exist n s.t. both 3^i*n±2 are primes for all i<m?

For all $m$ there exist $n$ s.t. both $3^in\pm2$ are primes for all $i<m$? I came up with the following question with a game. The game says: Start with an odd number $n$ greater than 3. In each ...

1
2 3 4 5
656