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

learn more… | top users | synonyms

1
vote
0answers
14 views

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

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 since the divisors of $6$ are $1$, $2$, ...
2
votes
1answer
65 views

Is the totient function $\varphi$ invertible?

As title, is the totient function $\varphi: \mathbb{N} \to \mathbb{N}$ invertible?
3
votes
2answers
62 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
25 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 ...
2
votes
0answers
40 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
8 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 ...
3
votes
2answers
81 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
27 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
4answers
42 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
2answers
73 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 ...
5
votes
3answers
104 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
34 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
41 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
39 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
42 views

Silly number theory questions I can't prove.

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+bs$, if I am restricted to $a,b \in \mathbb{N}$? To be more specific, I ...
3
votes
1answer
40 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
86 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
49 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
17 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 ...
1
vote
1answer
88 views

Show that $0=+0=-0$ [on hold]

I'm trying to prove that $0=+0=-0$. This is for a Digital Circuits class. At first I thought of showing that $0$ doesn't equals $+0$ and then arriving to a contradiction, but I'm stuck at this. Is ...
0
votes
1answer
49 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 ...
0
votes
0answers
29 views

Sum of digits of numbers in a range

Given an integer N. For each pair of integers (L, R), where 1 ≤ L ≤ R ≤ N we can find the number of distinct digits that appear in the decimal representation of at least one of the numbers L L+1 ... ...
2
votes
1answer
88 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
38 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 ...
-2
votes
0answers
47 views

Count Triangular Triplets [on hold]

Given a range [L,R] we need to calculate numbers of such triplets [A,B,K] which follows A+B=K where A,B are any two triangular numbers and K must be in an ...
0
votes
0answers
37 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 ...
0
votes
1answer
49 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
80 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
78 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
23 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 ...
2
votes
1answer
42 views

solve the diophantine equation: $x^3-3xy^2=z^3$

Let $ x,y,z$ be 3 integers greater than 1,if $x$ and $y$ are relatively prime, solve the diophantine equation: $x^3-3xy^2=z^3$.
1
vote
0answers
24 views

Proof of the formula for the number of components in all partitions of a given number

I have to show that this formula is the number of components in all partitions of number $n$: $$\sum_{i=1}^{n}\sum_{j=1}^{[n/i]}\sum_{k=0}^{n-ij}A_i(k) \cdot A_{j-1}(n-ij-k)$$ $A_k(n)$ is number of ...
1
vote
1answer
47 views

When is a sum of products of positive powers of 2 and 3 divisible by $2^b-3^n$?

Here we have a really tough exercise. Find all natural solution: $$\frac{\sum\limits_{k=1}^n 2^{a_k} 3^{n-k}}{c}+3^n=2^{b} ,\quad b\geq a_n; \quad a_k, b, c ,n\in \mathbb N $$ Any ideas, hints?
3
votes
3answers
61 views

Raising $2$ to the power of $2014^ {2013}$ modulo $41$

The question is as follows: $$2^{{2014}^{2013}}$$ Determine its remainder by division with $41$. I know that I need to use $\bmod 41$ and reduce the power somehow to something that can be solved ...
1
vote
3answers
55 views

Simplifying radical expressions such as $\sqrt{80}$

I am having trouble simplifying a radical expression, such as say...$\sqrt{80}$. What I do is firstly, I do 80/2, then 80/3, then 80/4, then 80/5...etc until I find the largest number that can be ...
5
votes
5answers
183 views

The number $(3+\sqrt{5})^n+(3-\sqrt{5})^n$ is an integer

Prove by induction that this number is an integer: $$u_n=(3+\sqrt{5})^n+(3-\sqrt{5})^n$$ Progress I assumed that it holds for $n$ and I tried to do it for $n+1$ but the algebra gets quite messy and ...
0
votes
2answers
101 views

General question about undergrad math classes? [closed]

I'm currently in Real Analysis 2, and while I'm doing pretty well, it's just so much time and effort to finish all the problem sets and do well on the exams. I only have a few math classes left for ...
1
vote
3answers
42 views

If $x$ leaves remainder $2$ when divided by $8$, what will the remainder be when $x + 9$ is divided by $8$?

If the positive integer $x$ leaves a remainder of $2$ when divided by $8$, what will the remainder be when $x + 9$ is divided by $8$? I love to put stuff into algebraic equations to make life ...
1
vote
3answers
39 views

Transcendental Union Algebraic = Irrational?

It is true that $\mathbb{R} = \mathbb{Q} \bigcup \overline{\mathbb{Q}}$ where $\mathbb{R}$ is the set of real numbers, $\mathbb{Q}$ is the set of rational numbers, and $\overline{\mathbb{Q}}$ is the ...
2
votes
2answers
74 views

Solution of an equation involving even integers

If $x$ is any positive even integer $> 1$. I compute: $$ c = x + x! $$ Now assume instead $c$ (even integer) is given, and I want to get back the value $x$. Is it possible to find a simple ...
1
vote
1answer
53 views

Show that there are infinitely many integers $n$ with a given number of divisors

Show that there are infinitely many integers $n$ with a given number of divisors, but at most finitely many $n$ with a given sum of divisors. Sorry no useful attempt this time, any help on ...
1
vote
1answer
24 views

“Descent” on binary quadratic forms?

Let's say I have the Diophantine equation $$ x^2+3n^2 = y^2+3z^2. \tag{$\star$} $$ where $n$ is a known integer, and we're trying to determine solutions in integers $x,y,z \ge 1$. Rewrite ($\star$) ...
3
votes
2answers
242 views

A number is a perfect square if and only if it has odd number of positive divisors

I believe I have the solution to this problem but post it anyway to get feedback and alternate solutions/angles for it. For all $n \in \mathrm {Z_+}$ prove $n$ is a perfect square if and only if $n$ ...
0
votes
0answers
37 views

Explanation of a proof of the existence of reclusive primes

The goal is to prove: For any given number $N$, there exists a prime number that is at least $N$ greater than the previous prime number and at least $N$ smaller than the following one. We call those ...
7
votes
4answers
400 views

There are finitely many maps on nonnegative integers satisfying $\phi(ab)=\phi(a)+\phi(b)$

How to show that there are finitely many maps $\phi:\mathbb{N}\cup\{0\}\to \mathbb{N}\cup\{0\}$ with the property that $\phi(ab)=\phi(a)+\phi(b)$ for all $a,b\in \mathbb{N}\cup\{0\}$.
0
votes
1answer
34 views

Value of an iterated sum

I am interested in the number of function evaluations required to numerically evaluate an iterated integral of the form $$ \int_0^t \int_{t_1}^t \cdots \int_{t_{n-1}}^t f(t_1,\ldots,t_n) dt_n\cdots ...
1
vote
3answers
50 views

Subgroup of matrices exercise

Let $G=\{\left( \begin{array}{ccc}1 & b \\ 0 & a \\ \end{array} \right) : a,b \in \mathbb Z_7, a \neq 0\}$. Find the order of $G$. For each prime $p$ such that $p$ divides $|G|$, find all ...
1
vote
1answer
25 views

Even numbers and Euler's Totient Function

If $m$ is even, $m|r$ and $\phi (r) \leq \phi (m)$, prove that $r=m$. I only knew the converse is also true $\phi (r) \geq \phi (m)$ but i dont know how the condition $m$ is even is gonna help, ...
1
vote
0answers
22 views

Powerful numbers in Pell solutions (or, more generally, any Lucas sequence)

There are several definitive results regarding perfect powers in the Pell numbers — e.g., the only perfect power is $P_7=169=13^2$. On the other hand, when it comes to powerful numbers, I've only ...
0
votes
0answers
19 views

Solving a recurrence relation with absolute values in it.

The recurrence relation is: Let $\{y_{j}\}_{j\in \mathbb{N}}$ be a sequence of integers and x a real number then define: $P_{1}(x):=y_{1}+(-1)^{1}|x-y_{1}|$ and the general j-step as ...