Stack Exchange Network

Stack Exchange network consists of 174 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
1answer
19 views

Prove that gcd(a,b)=dgcd(a/d,b/d). [duplicate]

I think the strategy for this problem would be i assume some arbitrary element is in gcd(a,b) and chase it into the rhs and then do it the other way around , but i am not sure how to even start this ...
0
votes
1answer
36 views

An isomorphism between $\mathbb Z_n \times \mathbb Z_m$ and $ \mathbb Z_{mn}$

I am reading these lecture notes and they suggest the following generalisation of a specific example for $\mathbb Z_2 \times \mathbb Z_3 \cong Z_6 $: There exists an isomorphism between $\mathbb ...
0
votes
0answers
34 views

Hard congruence equation with large residual.

So I want to explain how one would go about solving the equation $$y^{2019}\equiv 3571700849900719233 \quad (\text{mod} \ p),$$ where $p=2^{64}+13,$ which is the first prime after $2^{64}.$ ...
0
votes
2answers
20 views

Can you propose a theorem from these congruences?

Find the least positive residues of a) $6! \ (\mod 7)$ b) $10! \ (\mod 7)$ c) $12 ! \ (\mod 13)$ d) $16! \ (\mod 17)$ e) Can you propose a theorem from above congruent? My ...
-2
votes
1answer
32 views

What integer solutions does the equation $abc + abd + acd + bcd = efg + efh + egh + fgh$ have?

For which sets {$a,b,c,d$}, {$e,f,g,h$} do we have $abc + abd + acd + bcd = efg + efh + egh + fgh$?
-1
votes
1answer
24 views

Is the set of $n,m$ s.t. $2^n-3^m=1$ or $3^m-2^n=1$ finite?

Is the set of $n,m$ s.t. $2^n-3^m=1$ or $3^m-2^n=1$ finite? tried factoring but got nowhere, not sure what theorem or subject applies to this question. PS : no it is not a homework, but if a book has ...
2
votes
2answers
52 views

Prove: $2^b-1\mid{}2^a-1 \iff b\mid{}a$ [duplicate]

I figured we'd have to show $a=qb$ from $2^a-1=r(2^b-1)$ for $q,r\in\mathbb{Z}$ for the first implication and vice versa, how should I proceed from here?
1
vote
2answers
48 views

How do we find the general term from an infinite nested radical

I am struggling on how we definite infinite nested radical. Consider $ {\sqrt {2+{\sqrt {2+{\sqrt {2+{\sqrt {2+\cdots }}}}}}}}$ From what I have researched, I know we can consider the above ...
1
vote
4answers
44 views

If $p^4 | z^2$, then $p^2 | z$ for $p$ a prime and $z$ some positive integer.

Problem: Suppose that $p$ is a prime, and $z$ is some positive integer. If $p^4 | z^2$, then $p^2 | z$. Thoughts: If for some positive integer $a$, that $p^4 a = z^2$, then necessarily $p^2 \sqrt{...
1
vote
2answers
24 views

Given surface area of a cuboid, find it's integer side lengths.

Its a rather small problem once you've boiled it down to: $2(ab + bc + ca) = 100$ (the surface area of said cuboid) Now, I'm left with the equation: $ab + bc + ca = 50$, $3$ variables and $1$ ...
0
votes
1answer
26 views

An elementary problem concerning real nuumbers

Take any $y\in \mathbb{R}$, $r>0$ and let $I_{y,r}=(y,y+r)$. Consider the set $A=\bigcup\limits_{i=1}^\infty (i^2,i^2+1)\cup (-i^2,-i^2+1)$, how to explicitly write the set $A\cap I_{y,r}$ as a ...
0
votes
1answer
32 views

A question regarding primes and least common multiples

Let $p$ and $q$ be distinct primes. Show that the equation $\textrm{lcm}(a, b) = (p^2) q$ has fifteen solutions in positive integers $a, b$. Thanks for any help in advance as I don't know how to ...
0
votes
0answers
43 views

Triviality of $d|n$

I am currently confused on a problem in a practice set I have been given. It reads the following: Let $d$ be a positive integer and let $n$ be an integer. Prove that $d | n$ if and only if in the ...
0
votes
1answer
18 views

Greatest common divisor with $a \cdot s + b \cdot t = ggT(a,b)$

On the internet, I've seen the greatest common divisor with the notation $a \cdot s + b \cdot t = ggT(a,b)$ So for $a = 121$ and $b = 33$, the table is \begin{array}{|c|c|c|c|} \hline r& q & ...
5
votes
2answers
125 views

Prove that the product of any two numbers between two consecutive squares is never a perfect square

In essence, I want to prove that the product of any two distinct elements in the set $\{n^2, n^2+1, ... , (n+1)^2-1\}$ is never a perfect square for a positive integers $n$. I have no idea on how to ...
0
votes
3answers
52 views

Modular multiplicative inverse proof

Does the concept of modular multiplicative inverse require a proof or is it taken as a definition? Suppose $5/4 \equiv 3$ (mod $7$). Can that even be written in the standard $a = bq + r$ notation ...
2
votes
2answers
81 views

is there a faster method to calculate $1/x$ ($x$ an integer) than this?

I gave this stackexchange a second go. Is there a faster way to calculate $1/x$ than the following: Calculate $100/x$ (.or other arbitrary positive power of $10$) with remainder Write multiplier in ...
0
votes
1answer
69 views

Prove that $\forall n > 1, n \nmid 2^n-1$. [duplicate]

$$\forall n > 1, n \nmid 2^n-1$$. I have proved that this would not be divisible by some even $n$ but I'm unable to do it for odd $n$.
3
votes
3answers
111 views

Numerical example for $\gcd(a,b)=\prod p_i^{\min(a_i,b_i)}$

I'm actually having trouble understanding the above corollary. Can anyone please provide a numerical example of that corollary? Thank You So Very Much in advance. Corollary If $a=\prod p_i^{a_i}$ ...
0
votes
2answers
40 views

if $n_{3}\equiv1\pmod3$ and $n_{3}\mid7$ then $n_{3}\in \{1,7\}$

It rather easy/basic question and I feel ashamed asking it but I can't figure it out. If I know that $n_{3}\equiv1\pmod 3$ and $n_{3}\mid 7$, how to calculate $n_3$? I know that the answer is $n_{3}\...
-1
votes
2answers
69 views
2
votes
2answers
62 views

Find at least $5$ integers $n$ such that $\varphi(n)=16$

Let $\varphi(n)$ denote Euler's totient function. Find all integers such that $\varphi(n)=16$. Answers given were $17,32,34,40,48.$ I am thinking a generalisation of this problem: is there a way ...
6
votes
2answers
84 views

Is there any elementary solution for this problem on colored interval?

The problem is as following. Assume $m,n$ are two coprime odd numbers, consider the interval $[0,mn]$. We cut the interval by $m,2m,\ldots,(n-1)m$ and $n, 2n,\ldots, (m-1)n$ into $m+n-1$ pieces of ...
6
votes
1answer
55 views

show $p\mid 2^n-n$ for infinitely many $n$ [duplicate]

Show that $p\mid 2^n-n$ for infinitely many $n$. $p$ is a prime and $n$ is an integer. I tried using Fermat's little theorem and got $2^p-p\equiv2\pmod p$ and $2^{p-1}-(p-1)\equiv2\pmod p$. So I can'...
1
vote
1answer
48 views

Is there any natural number triangle whose inscribed circle's radius is $1$ except length $(a,b,c)=(3,4,5)$?

Is there any natural number triangle that inscribed circle's radius is $1$ except length $(a,b,c)=(3,4,5)$? I found that there are no right triangle except $(3,4,5)$. Thm. There are only one ...
1
vote
0answers
12 views

How does $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ follow from “if all these powers of $2$ agree”?

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Shor, 1995) [p. 15] To find a factor of an odd number $n$, given a method for computing the order $...
-3
votes
2answers
82 views

What is the cardinal number of $\lim_{n\to\infty}\mathcal{X}_{n}=\left\{ 1,2,\dots,n\right\}$?

What is the cardinal number of $\lim_{n\to\infty}\mathcal{X}_{n}=\left\{ 1,2,\dots,n\right\}$? This is not the same question: Is $\lim\limits_{n\rightarrow\infty} n$ comparable to $\aleph_0$?. That ...
2
votes
0answers
30 views

Constraints over $e$ for $x^n \equiv a (2^e) $ to be solvable

I'm reading "A classical intro to modern number theory" by Ireland & Rosen, in which Proposition 4.2.4 proof is left as an exercise. Let $n=2^lk $ with $k $ odd, assuming that $x^n\equiv a (2^e) $...
0
votes
2answers
26 views

coprime integers come in pairs [duplicate]

Suppose $k$ and $n$ are integers such that $1\leq k<n$ and $\gcd(n,k)=1$. Why is it that $\gcd(n-k,n)=1$ as well? $\gcd(n,k)=1$ implies that there exist integers $a,b$ such that $an+bk=1$, but I ...
1
vote
1answer
23 views

Understanding this proof regarding quadratic residues

Let $p$ be an odd prime and let $Q_p$ denote the quadratic residues modulo $p$, $N_p$ the non-residues modulo $p$. Let $X$ be some subset of $p$. Then, $$ q X \equiv X mod (p) \hspace{2mm}\forall q \...
2
votes
2answers
47 views

For $F(n)$ the $n$-th Fibonacci number, is $F(a)F(b)-F(a+1)F(b-1)$ always $\pm F(m)$ for some $m$?

For $F(n)$ the $n$th Fibonacci number, the expression $$F(a)F(b)-F(a+1)F(b-1)$$ seems to be $\pm F(m)$ for some $m$. I can't specify $m$ or the sign in terms of $a,b,$ and have not tried it out ...
2
votes
3answers
61 views

Show that if $\gcd(abc,d^2)=1$, then $\gcd(a,d)=\gcd(b,d)=\gcd(c,d)=1$.

Let $a,b,c$ be integers. Show that if $\gcd(abc,d^2)=1$, then $\gcd(a,d)=\gcd(b,d)=\gcd(c,d)=1$. Here is my way of approaching this question: Suppose $\gcd(abc,d^2)=1$, there exist integers $x,y$ ...
2
votes
1answer
51 views

Find a 10 digit number that contains all digits from 0 to 9 once, starts with a 3, and is also divisible by all whole numbers from 2 to 18

Trial and error is always an option, but this question is from a timed math competition sheet, so it shouldn't take that long. Where do I start? Edit: As far as the competition aspect is involved, a ...
1
vote
1answer
39 views

How exactly does finding a square root of $1$ modulo $N$ enable us to factor $N$?

The Wikipedia article on Shor's algorithm says: The aim of the algorithm is to find a square root $b$ that is different from $1$ and $-1$; such a $b$ will lead to the factorization of $N$, as in ...
0
votes
1answer
41 views

Prove that there does not exist ${ace\over bdf}={m\over n}$ where $m,n\in\mathbb{Z^+}$ and $m+n\lt101$

Let $a,b,c,d,e,f\in\mathbb{Z^+}$ where $a+b=c+d=e+f=101$. Prove that there does not exist ${ace\over bdf}={m\over n}$ where $m,n\in\mathbb{Z^+}$ and $m+n\lt101$. I tried to attempt this question but ...
1
vote
1answer
63 views

Find all primes $p$ for which there are positive integers $x, y$ such that $p+1=2x^2$ and $p^2+1=2y^2$ [duplicate]

Find all primes $p$ for which there exist positive integers $x, y$ such that $p+1=2x^2$ and $p^2+1=2y^2$. I have tried coming up with an equation for $p$ or $p^2$ and this is what I've got $p=2x^2-1$...
2
votes
1answer
57 views

does this way of grouping numbers have a name?

so this is a system i made, and i was wondering if someone had explored it before, and if it had a name. you start with a list of natrual numbers. you then remove every other number and i will call ...
1
vote
0answers
52 views

Discrete mathematics - Rubiks cube permutation and unique states.

Define a move to be a $90$ degree turn of $1$ of the $6$ sides of the cube clock-wise or counter-clockwise. So for a $3\times 3\times 3$ cube I know that the number of possible unique states ...
2
votes
4answers
76 views

Finding rational solutions for $3x^2+5y^2 =4$

I want to calculate all rational solutions for $3x^2+5y^2 =4$. However, I think that there are no rational solutions because if we homogenize we get $3X^2+5Y^2 =4Z^2$ and mod 3 the only solution is $Z=...
0
votes
0answers
41 views

Permutations of quadratic residues modulo $p$

When bending the square $[0,n[\times[0,n[$ to a torus, the quadratic residues $k^2\ \%\ n$ — with $0 < k < n$ and $a\ \%\ b$ meaning $a$ modulo $b$ — lie on a parabola $P_1$ with ...
1
vote
3answers
22 views

Let $x,y$ be coprime integers. If $z$ is a multiple of $x$ and $y$ then $z$ is a multiple of $xy$. [duplicate]

Let $x,y$ be coprime integers. I want to prove that if $z \in \mathbb Z$ is a multiple of $x$ and $y$ then $z$ is a multiple of $xy$. I know that $\exists r,s,m_1, m_2 \in \mathbb Z$ s.t. $$z=m_1x=...
1
vote
4answers
98 views

a,b,c are three real numbers where $a + \frac{1}{b} = b + \frac{1}{c} = c + \frac{1}{a}$. Now $abc$ = ? Here will the answer be a number? [duplicate]

I want to know whether it is possible to get a real number (not an algebraic expression) as the product of $a$, $b$ and $c$. I tried for a long time and this is what I got. $$3abc = a^2 b + b^2 c + ...
2
votes
4answers
79 views

Dividing both sides of congruence

I am having trouble understanding division in modular arithmetic. I didn't manage to find any good resources online on that. Usually it is explained like this: If we have $a \equiv b$ (mod $n$) ...
-1
votes
1answer
62 views

Find whole number solutions

Sorry if this is a dupe or too basic, the similar questions seemed to have extra requisites tacked on. Background: Solving the Cheryl's birthday riddle sequel maybe I'm on the right track, maybe not, ...
1
vote
1answer
70 views

What is the value of $5 * 6$ in the following patttern?

Mr. Pascal built a computer for multiplying numbers and named it "Ramanujan". But Ramanujan multiplies $(3, 5), (2, 4), (3, 4)$ and $(4, 7)$and results are $17, 10, 14$ and $34$. If Ramanujan ...
-1
votes
1answer
43 views

How many digits do I need to determine if the product of a whole number an irrational number is odd or even? [on hold]

So, say you have a really huge whole number like $5^{2000}$ and an irrational number like $\sqrt(5)$. If you were two multiply the two would you get an even or odd number after rounding to the ...
11
votes
0answers
192 views

Why is counting the number of least prime factors of a sequence of consecutive integers insufficient to resolve Legendre's Conjecture?

I've been thinking a long time about Legendre's Conjecture. A few nights ago, I came across the following argument which is of course too simple to be true. I would greatly appreciate if someone ...
1
vote
0answers
68 views

A Groovy Number Theory Problem [on hold]

A number n is groovy iff the sum of the digits of n(2n+1) is 2018. Do such numbers exist and, if so, what are they?
0
votes
0answers
34 views

Book about Prime numbers [duplicate]

Is there any book that tells theorems about prime numbers with proofs. I know undergraduate calculus. I need a book that explains everything in detail.
0
votes
1answer
55 views

Guess and Prove by induction a formula for the $n$-th element in a sequence $b_n$ [on hold]

So I've been given a sequence. The sequence $b_0,b_1,b_2$, ... is defined as follows: $b_0 = 0$, $b_1 = 1/2$, and for integers $n \ge 2$, $b_n = \sqrt{b_{n-1}b_{n-2}} + \frac{3n}{2} - 1.$ My ...