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

learn more… | top users | synonyms (1)

3
votes
2answers
66 views

Find the 6 Digit Number

$N$ is a 6 digit Natural number such that its sum of the digits is $43$. Find $N$ if Exactly One of the statements below is False: $(1)$ $N$ is a Perfect Square $(2)$ $N$ is a Perfect Cube $(3)$ N ...
0
votes
4answers
71 views

Solve $c^2-b^2-a^2=2N$

Is there anyone that can help solving this equation: $c^2-b^2-a^2=2N$ where $a,b,c,N$ are natural numbers. Edit: We need to express $a,b,c$ for a certain $N$. Regards
48
votes
4answers
2k views

Does the string of prime numbers contain all natural numbers?

Does the string of prime numbers $$2357111317\ldots$$ contain every natural number as its sub-string?
3
votes
1answer
127 views

How to mark rational points on a sphere

I found this picture on mathoverflow, which I find very intriguing and so I like to know how to draw such an image with a simple computer program. To calculate the rational point, I can draw a line ...
2
votes
1answer
64 views

decomposition into three squares

Doing a coding assignment. And it's basically having a user enter $n$. Then I need to provide (If it exists) $$n = x^2 + y^2 + z^2.$$ Not really sure how to approach this. Any ideas?
0
votes
0answers
20 views

How solve the equation $a^x+\left(2a+1\right)^y=\left(a+1\right)^z$ for $a\in N - \{1\}$ and $x,y,z\in N\cup\{0\}$?

How solve the equation in natural numbers $a^x+\left(2a+1\right)^y=\left(a+1\right)^z$ for $a\in N - \{1\}$ and $x,y,z\in N\cup\{0\}$?
0
votes
1answer
91 views

Proof of Floyd Cycle Chasing (Tortoise and Hare)

I am looking for a proof of Floyd's cycle chasing algorithm, also referred to as tortoise and hare algorithm. After researching a bit, I found that the proof involves modular arithmetic (which is ...
4
votes
1answer
31 views

Maximum operation order for a set of integers

Say we are given the positive integers $[1,1,2,2,3]$ We want to know what the maximum number is using only the operators $+$, $\times$. For this set the maximum operation is ...
1
vote
3answers
47 views

Greatest value of digits from adding numbers

$\begin{array} &&N&R\\ +&R&N\\\hline A&B&C \end{array}$ The addition problem above is correct. If N, R, A, B, and C are different digits, what is the greatest possible ...
1
vote
3answers
110 views

The final digit of fourth powers

I am working on "Elementary Number Theory" By Underwood Dudley and this is problem 13 in Section 4. The question is "What can the last digit of a fourth power be?" I got the correct answer but I'm ...
3
votes
0answers
49 views

Combinatorial interpretation of an equality

In a recent project, I came up with the following equality which turned out to be extremely useful for counting conjugacy classes in certain division algebras (I won't go into the details here, it's ...
3
votes
1answer
68 views

Any nice way to find number number of single digit ordered pairs $(a, b)$ such that $a!b! \gt a!+b!$

I have listed them all by brute force : a = 0,1 : no solutions a = 2 : b = 3,4,5,...9 c = 3 : b = 2,3,4...9 I'm wondering if there is a clever approach to ...
4
votes
2answers
81 views

Prove $\frac{ab}{1+c^2}+\frac{bc}{1+a^2}+\frac{ca}{1+b^2}\le\frac{3}{4}$ if $a^2+b^2+c^2=1$

Ff $a,b,c$ are positive real numbers that $a^2+b^2+c^2=1$ ,Prove: $$\frac{ab}{1+c^2}+\frac{bc}{1+a^2}+\frac{ca}{1+b^2}\le\frac{3}{4}$$ Additional info:I'm looking for solutions and hint that ...
6
votes
3answers
111 views

Does the sum of the reciprocals of all primes of the form $4k+1$ converge?

Let $S=\{p\in \mathbb{Z}^+ : p\ \text{is prime and}\ p\equiv 1 \mod \ 4\}.$ Is $\displaystyle\sum_{p\in S}\frac{1}{p}$ finite or infinite, and where can I find more information about it?
0
votes
1answer
60 views

The number of prime divisors of any number

How can one show that the number of prime divisors of any number less than $2^n$ is at most $n$.
5
votes
2answers
99 views

How to solve the congruence $x^{59} \equiv 604 \pmod{2013}$?

$$x^{59} \equiv 604 \pmod{2013}$$ Could somebody give me any clue? I have no idea how to start. I see that $59$ is prime.
2
votes
2answers
89 views

Irrationality of $\sqrt{3}$ [duplicate]

No doubt an easy question: I'm trying to follow Wikipedia's (second) proof of the irrationality of $\sqrt{3}$ and it relies on the notion that since $3n^2 = m^2$ is divisible by 3 then so is $m$. Why ...
-1
votes
3answers
73 views

Solve the diophantine equation $ ax+by=xyc$

Let $a,b,c$ be non-zero co-prime integers such that $a+b \neq c$, and $ x.y\neq 0$, solve the diophantine equation $ ax+by=xyc$.
0
votes
2answers
57 views

Solve this number theory problem without plugging in

$a>b$ $b<c$ $a=2c$ If a,b, and c represent different integers in the statements above, which of the following statements must be true? I. $ac>b^2$ I know that the above statement is true ...
3
votes
2answers
84 views

Is there an integer $N>0$ such that $\varphi(n) = N$ has infinitely many solutions?

Let $\varphi: \mathbb{N} \to \mathbb{N}$ be the totient function. Is there an integer $N > 0$ such that there are infinitely many integers $n > 0$ such that $$\varphi(n) = N?$$
1
vote
0answers
44 views

Are (odd) perfect numbers divisible by a repdigit (in another base)? How about by a repunit?

[This has been cross-posted to MO.] A positive integer $N$ is said to be a perfect number if $$\sigma(N) = 2N,$$ where $\sigma(x)$ is the sum of the divisors of $x$. For example, $6$ is perfect ...
3
votes
1answer
99 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
3
votes
2answers
94 views

Finding $23! 7! \bmod 29$ using Wilson's Theorem

I'm trying to reduce $23!\,7! \bmod 29$. I used Wilson's Theorem to get $23!(120)\equiv 1 \pmod{29}$. I then solved $120a\equiv 1 \pmod{29}$ and got $a\equiv 22$. I then computed $7! \pmod {29}$. ...
2
votes
1answer
54 views

The perimeter of triangle $ABC$ where $|BC|=293$, $|AB|$ is a square, $|AC|$ is a power of $2$, and $|AC|=2|AB|$

In triangle $ABC$ length of side $BC$ is $293$ (a prime). If length of side $AB$ is a perfect square, length of side $AC$ power of 2 and $AC$ twice length of $AB$, find the perimeter. Kind of ...
5
votes
0answers
130 views

Diophantine: $x^3+5=y^5$

Find all integers $x$ and $y$ such that $x^3+5=y^5$. I found this after solving the equation $3^a+5=2^b$. For this equation, since $(a,b)=(3,5)$ is a solution, it is possible to write it as ...
1
vote
2answers
264 views

Infinite geometric progression involving square terms

The sum of an infinite geometric progression is 15 and the sum the squares of these terms is 45. Find the series. The formula for sum of infinite GP is $\frac{a }{1-r} $ and I got two equations ...
4
votes
2answers
118 views

Why is there a 'missing' $1$ in the Euler–Mascheroni constant?

It is easy to show that: $$ \sum_{k=1}^n \frac{1}{k} > \ln(n+1), $$ but the Euler–Mascheroni constant is defined as: $$ \gamma = \lim_{n \to \infty} \left( \sum_{k=1}^n \frac{1}{k} - \ln(n) ...
1
vote
1answer
35 views

$\Pi_{1}^{k}(p_{j} - 1) \mid (\Pi_{1}^{k}p_{j} - 1)$?

Do there exist an integer $k \geq 2$ and distinct odd primes $p_{1}, \dots, p_{k}$ such that $$\Pi_{1}^{k}(p_{j}-1) \mid (\Pi_{1}^{k}p_{j} - 1)$$
2
votes
2answers
118 views

coin problem with two coins, inductive proof

Adjustment This proof is flawed. I want to ask something about the coin problem with two coins. Let $a,b$ be to numbers in $\mathbb{N} \setminus \{0\}$ (elsewhere I include zero) which have no prime ...
2
votes
4answers
50 views

If $n > 0$ is an even composite integer, then $\varphi(n)$ is even? [duplicate]

If $n > 0$ is an even composite integer, is the corresponding totient $\varphi(n)$ also even? I found that it is not the case for $n$ odd; for $\varphi(15) = 8$.
2
votes
3answers
104 views

Equivalence class for the relation of having the same set of prime divisors

For an integer $n\in \mathbb{N}$ define $P(n) = \{p : p \mid n \text{, where $p$ is a prime} \}$. For example $P(12)=\{2,3\} $ and $P(1)=\emptyset$. Question: Consider the relation $R$ on ...
1
vote
1answer
97 views

Natural and Real sets of numbers, which one is bigger than another?

From the years ago, it has always been this question in my mind which a teacher of high school talked about in a class but I never found it's correct answer. We have set of natural numbers ...
7
votes
3answers
158 views

How to prove that $53^{103}+ 103^{53}$ is divisible by 39?

This is a problem in my number theory textbook. It is based on modular arithmetic but im not getting how to start off to prove this. Please give me some hints on how to solve it.
1
vote
0answers
48 views

Multiplicative order: an exercise

I've got this problem: Determine an integer with (exactly) multiplicative order $22$ mod $1331$ Is there a general way to procede in any case with this kind of exercises? Thank you!
1
vote
2answers
49 views

Proof that the congruence relation on $\mathbb Z$ is transitive (attempt shown)

I have answered this question to the best of my knowledge but somehow I feel as if I am missing something? Can I further prove this statement or add anything to it? Question: Let $m \in \mathbb ...
2
votes
1answer
47 views

Generators of the group of integers exercise

Let $a,b \in \mathbb Z$. (1) Prove that $\{a,b\}$ is a system of generators of $\mathbb Z$ if and only if $(a,b)=1$, where $(a,b)$ is the greatest common divisor between $a$ and $b$. (2)Show that ...
2
votes
1answer
76 views

If $\gcd(r,s)=1$, which numbers can be written as a linear combination $as+br$ with $a,b$ nonnegative?

I know if $gcd(r,s)=1$ then $1=as+bs$ for some intgers $a,b$. Here's what I want to know: which numbers can be written as $as+br$, if I am restricted to $a,b \in \mathbb{N}$? To be more specific, I ...
2
votes
1answer
47 views

Modular Arithmetic and Zero Divisors

If $ab \equiv 0\pmod n$ then $a \equiv 0\pmod n$ or $b \equiv 0\pmod n$, when $n$ is prime. I know that $n\mid(ab-0) = ab$ so it obviously divides $a$ or $b$ but that's not necessarily when $n$ is ...
2
votes
2answers
106 views

How to show that an infinite decimal is equal to a unique real number?

I don't understand how the proof above shows that two distinct real numbers correspond to different infinite decimal. All I got out of the explanation is given any two distinct real numbers $a$ and ...
0
votes
2answers
83 views

Continuous differentiable spline or function resembling floor

I'd need any (real-valued) function (whatever meets the following description at least approximately) continuous and thrice differentiable everywhere (or twice if 3 not possible), with the following ...
2
votes
0answers
20 views

proof of: $\gcd(n^a - 1, n^b - 1) = n^{\gcd(a,b)}- 1$ [duplicate]

I have a problem with following proof: $$\gcd(n^a - 1, n^b-1) = n^{\gcd(a,b)} - 1 $$ The only thing that I can show is fact: $$n^{\gcd(a,b)} -1 | n^a - 1$$ $$n^{\gcd(a,b)} -1 | n^b - 1$$ And ...
0
votes
1answer
56 views

Prove that $p\mid b$ or $p\mid c$

If $a,b,c$ are integers and $p$ is a prime that divides both $a$ and $a +bc$, prove that $p\mid b$ or $p\mid c$. The way I'm trying to think of it, and I might be completely wrong, is using a theorem ...
1
vote
1answer
94 views

Rounding number

I have the formula: r(n) = (9t(1+n)-10^t+1)/9 where t = lowerboundof(log10(n)) What's the math symbol describing lower and upper bound of a non-integer positive ...
0
votes
0answers
45 views

Solutions of integer equality

I cannot find a solution of following integer equation: Given any $n,r\in\mathbb{N}^{+}$ such that $n\geq \dbinom{r+1}{2}$. How many positive integer solutions of the following equation ...
0
votes
0answers
48 views

Positive integer solutions to $p^2 + q^2 \leq 4^k$

Earlier this evening (morning), I posted a question about showing that a finite number of dyadic squares can fill up an arbitrary proportion of the unit disk. I'm sure there are better ways to prove ...
5
votes
3answers
435 views

How prove this inequality $\sum\limits_{cyc}\frac{1}{a+3}-\sum\limits_{cyc}\frac{1}{a+b+c+1}\ge 0$

show that: $$\dfrac{1}{a+3}+\dfrac{1}{b+3}+\dfrac{1}{c+3}+\dfrac{1}{d+3}-\left(\dfrac{1}{a+b+c+1}+\dfrac{1}{b+c+d+1}+\dfrac{1}{c+d+a+1}+\dfrac{1}{d+a+b+1}\right)\ge 0$$ where $abcd=1,a,b,c,d>0$ I ...
0
votes
1answer
80 views

Prove that the Goldbach conjecture implies that for each even integer $2n$ there exist integers $n_1$ and $n_2$ with $\sigma(n_1) + \sigma(n_2) = 2n$

My try so far : If goldbach conjecture is true, then every even number can be expressed as sum of two prime numbers : $p_1 + p_2 = 2n$ How should I proceed further ?
3
votes
2answers
94 views

What is the meaning of this Wolfram Alpha result when calculating $3^p = 4^q$?

I would like to know are the some $p \in \mathbb{N}$ and $q \in\mathbb{N}$ for $3^p = 4^q$ except the trivial $p = q = 0$. So, I entered the expression into Wolfram Alpha, which returned the result ...
3
votes
2answers
83 views

$\sqrt{\frac{15}{11}}$ continued fraction

I know how to find a continued fraction representation of rationals and quadratic irrationals, but I'm not sure how to proceed with square roots of rationals. For example, I want to know how to get: ...
0
votes
0answers
29 views

What are some [mostly trivial] Pell transformations?

Euler looked at some transformations which turned one Pell[-type] equation into another. Example 1: $$u^2-av^2=-1 \quad\iff\quad (2u^2+1)^2-a(2uv)^2=1.$$ Example 2: $$u^2-av^2=-2 \quad\iff\quad ...