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

learn more… | top users | synonyms (1)

0
votes
1answer
30 views

Question on general analysis of Number and Perfect squares

How many two-digit positive integers N have the property that the sum of N and the number obtained by reversing the order of the digits of N is a perfect square? Answer given is 8.
3
votes
0answers
19 views

Product of the Euler phi function [duplicate]

Prove the following statement: If $n, m\in\mathbb{Z} $ and $g=$gcd$(n, m) $ then is $$\varphi(m, n) =\frac{ \varphi(m) \varphi(n) g} {\varphi(g)}. $$ Hint: Prove the statement with induction above ...
1
vote
1answer
21 views

Conditions required for Inequality to hold

Given that $0 \leq X \leq x \leq y \leq Y < \infty$, I am interested to know the condition whereby $\frac{\sqrt{y}-\sqrt{x}}{\sqrt{y}+\sqrt{x}} \leq \frac{\sqrt{Y}-\sqrt{X}}{\sqrt{Y}+\sqrt{X}} $ ...
3
votes
2answers
158 views

Find all integer solutions to $a+b+c|ab+bc+ca|abc$

As you can see from the title, I am trying to find all integer solutions $(a,b,c)$ to $$(a+b+c) \ \lvert\ (ab+bc+ca) \ \lvert\ abc$$ (that is, $a+b+c$ divides $ab+bc+ca$, and $ab+bc+ca$ divides ...
3
votes
1answer
156 views

Polynomials and Arithmetic

Consider the polynomial $$p(x) = a_0 + a_1x + a_2x^2 + · · · + a_nx^n$$ where $a_0, a_1, . . . , a_n ∈ \Bbb Z$. Show that if $p(x_i) = 7$ for 4 distinct integers $x_0, x_1, x_2, x_3$, then $p(z) \neq ...
3
votes
1answer
20 views

Congruences and solution repeat intervals

I'm teaching myself about congruences, and I've done quite a few examples, but the answers to two problems have me confused. I understand $$3x \equiv 5 \pmod{7}\quad \Rightarrow\quad x \equiv 4 ...
0
votes
0answers
43 views

Inequality between two sums of numbers of divisors

Let $D_b(m)$ be the number of divisors of $m$ that are less than $b$. Neil Sloane has suggested that the number of binary quadratic forms $Ax^2 + Bxy + Cy^2$ with integral coefficients, discriminant ...
0
votes
0answers
40 views

Ensuring all $n$ in $\varphi(n)=x$

For Euler's totient function $\varphi(n)=x$ and any single known $x$, how can I prove that a set of $n$'s is complete? For instance, given $x=28$, $n\in\lbrace29,58\rbrace$. How to prove that no ...
0
votes
0answers
49 views

Is there a field of mathematics that deals with the strange properties of numbers?

This blog thread lists lots of strange number properties... https://www.quora.com/What-is-the-most-beautiful-number-and-why Is there a field of mathematics that deals with these strange number ...
1
vote
2answers
59 views

Asymptotics of $\sum_{n\leq x}d(kn)$ where $k$ is composite

As shown by @NoamD.Elkies here, $\sum_{n \leq x} d(kn)$ can be reduced to a linear combination of values of $D$ at multiples of $x$ (where $D(x)=\sum_{n\leq x}d(n)$ is the sum of the number of ...
0
votes
2answers
93 views

Find all triples of non-negative Integers $a,b,c$ such that $a!b!=a!+b!+c!$ [duplicate]

Exactly what it says in the Title; not much development from there :/
1
vote
2answers
24 views

Prove: If $a|c \wedge b | c \wedge (a, b) = d \Rightarrow ab | cd$

I know that $(a,b)=d \Rightarrow ma+bn=d, (m,n\in Z)$. $ma+bn=d/*c \Rightarrow cma+cnb=cd$ And I'm kinda stuck here. Any help or hint is appreciated.
1
vote
1answer
35 views

Can class number $h(d)$ equal to zero for some $d$?

We know that $L(1, \chi)$ is related to the class number $h(d)$ with a constant. And this is one way that we can prove $L(1, \chi)$ not vanish on $s = 1$. What confused me is: we know that class ...
1
vote
1answer
17 views

Any subgroup $H$ (or ideal) in $\mathbb{Z}$ is of the form $(m) = m\mathbb{Z}$ for some $m\in\mathbb{Z}$

Any subgroup $H$ (or ideal) in $\mathbb{Z}$ is of the form $(m) = m\mathbb{Z}$ for some $m\in\mathbb{Z}$. Proof: Suppose $H=\{0\}$, then $H=(0)$. Now suppose $H\not=\{0\}$. Then there are ...
1
vote
1answer
33 views

use the lines through the point (1 1) to describe all the points on the circle $x^2 + y^2 = 2$ whose coordiates are rational numbers

a) use the lines through the point (1 1) to describe all the points on the circle $x^2 + y^2 = 2$ whose coordiates are rational numbers. b) what goes wrong if you try to apply the same procedure to ...
-5
votes
3answers
62 views

Are there a closed form of near solutions to the equation: $2\sigma(n)=3n$? [closed]

I would like to check the solution of this equation: $$2\sigma(n)=3n$$ where $\sigma(n)$ is the sum divisor function. Note: I know only $n=2$ is a theortitical solution, are there a closed form of ...
3
votes
1answer
70 views

What is irrational number with the least/lowest irrationality?

The golden ratio has been called as "the most irrational number", based on a particular method called a continued fraction method. Using this continued fraction method the golden ratio has been stated ...
1
vote
0answers
41 views

What is the smallest karanayan elite integer?

Let s(n) = the sum of the digits of n, and let d(n) = number of digits of n (with non negative integers n). A karanayan elite integer is a positive integer of the form $10^{8+9k}+8+9k$ that can be ...
0
votes
0answers
64 views

Elementary dvisibilty problem involving power sums.

Prove that $1^n + 2^n + \cdots + m^n$ does not divide $(1+2+ \cdots +m)^n$ for any even integer $n\geq 2$. For $n\leq 4$, the result easily follows from the relevant identities. For $n\geq 6$, i ...
-4
votes
3answers
55 views

why $10$ in any base number system written as $10?$

I am a student trying to write an article in number system can same one give me an idea why $10$ in any base number system written as $10$ $?$
1
vote
1answer
22 views

Prove $2^a+1\mid 2^{ab}+1$ if $2\nmid b$, $a,b\in\mathbb{Z}^{+}$

Prove that $2^a+1\mid 2^{ab}+1$ if $2\nmid b$, $a,b\in\mathbb{Z}^{+}$. I tried Euclidean Algorithm: $\gcd(2^a+1,2^{ab}+1)=\gcd(2^a+1,2^{ab}-2^a)=\gcd(2^a+1,2^a(2^b-1))=\gcd(2^a+1,2^b-1)$ but I'm not ...
2
votes
1answer
34 views

Mersenne number divisible by twin primes

I am trying to determine the smallest odd n > 1 where the Mersenne number $2^n - 1$ is divisible by twin primes p and q with $p<q$. If n were even, by inspection, $M_4$ is divisible by 3 and 5 but ...
2
votes
1answer
37 views

Proving an implication

Let $x, y, n \in \mathbb N $ where $ x,y \gt 1$ and $2^n + 1 = xy$. Let $a \in \mathbb N.$ Prove: a) $ 2^a \mid(x-1) \Rightarrow a< n$ b) $ 2^a \mid(x-1) ↔ 2^a \mid(y-1)$ For a) I have: For ...
0
votes
2answers
24 views

How do i show this :for every prime $p> 3$ and every integer $k\geq1$ ,${p}^{4k}=1\mod3$?

There are many formula which are a multiple of $3$ for example $n^3+2n$ ,I accross this formula " ${p}^{4k}=1\mod3$" after some computations in WA then My question here is: How do i show this if it ...
1
vote
1answer
48 views

Solution to $p^3-p+1=a^2$

What are the solutions to $p^3-p+1=a^2$ where $p$ is prime and $a$ is natural? I found the solutions: $p=3$ and $a=5$ $p=5$ and $a=11$ and one solution when $p$ is not a prime: $p=56$ and $a=419$, ...
0
votes
1answer
29 views

Showing that $\operatorname{lcm}(a,b)$ is the unique positive generator of $(a) \cap (b)$

Let $a,b \in \mathbb{N}$. $l>0$ is the unique positive generator of the ideal $(a) \cap (b)$. Show that $l = \frac{ab}{d}$ where $d = gcd(a, b)$. I am stuck on this problem. $(a)=\{na: n \in ...
-4
votes
1answer
40 views

Find a positive integer. [closed]

Find a positive integer such that half of it is square,a third of it is a cube,and a fifth of it is a fifth power.
2
votes
4answers
60 views

Induction: Prove that $5^{3n} + 7^{2n-1}$ is divisible by $4$

Prove that $5^{3n} + 7^{2n-1}$ is divisible by $4$ for all $n \in \mathbb{N}$. For $n=1$, $\Rightarrow 5^3 + 7^1 \Rightarrow 132 \mid 4$ (which is divisible by $4$) Let us assume given equation ...
1
vote
1answer
30 views

lcm of orders of reduced residue classes of $1001$

By Euler's theorem, I know that all orders of reduced residue classes of $1001$ must divide $\phi(1001) = 720$. However, by a computer program, I know that the lcm of the orders of all $720$ reduced ...
2
votes
2answers
42 views

$a_k$ is a countable sequence of positive numbers st. $gcd(a_1,a_2,…)=1$, show exists a finite subsequence $a_{i_1},a_{i_2},…,a_{i_n}$ with gcd 1

The question is, Let $a_k$ be a countably infinite sequence of positive numbers st. $\gcd(a_1,a_2,...)=1$, does it exist a finite subsequence $a_{i_1},a_{i_2},...,a_{i_n}$ with ...
0
votes
0answers
13 views

$Φ_n$ is Euler group, $n> 2$ is an integer, and $m$ the number of solutions of the equation $x^2 = 1$ in the ring $Z_n$.

Prove $$\prod_{i ∈ Φ_n} i=(-1)^{\frac{m}{2}}$$ Then what becomes this identity if $n$ is a prime number? I know that if $x^2=1$, we pair the number with its inverse modulo $n$ in the ...
0
votes
1answer
25 views

What does this type of “division summation” notation mean?

$$\sum_{p | k} f(p)$$ What does this type of summation actually mean? Can you give me an example(s) with $p=1, 2$?
0
votes
1answer
41 views

Is there an explicit formula for the expression $(a\mathbb{Z}+b) \cap (a'\mathbb{Z}+b'),$ not involving $\cap$?

Thinking of $\mathbb{Z}$ as a ring, the ideals of $\mathbb{Z}$ are precisely those subsets of the form $a\mathbb{Z}.$ Hence intersections of ideals can be computed by taking lowest common multiples. ...
1
vote
2answers
32 views

HCF LCM Question

$540= 2^2 \times 3^3 \times 5$ Find the smallest positive integer $K$ such that $\frac{540}{k}$ is a cube number .
1
vote
2answers
29 views

Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients?

Suppose $d$ is a common divisor of two numbers $a_0$ and $a_1$, can $d$ be written as a linear combination of $a_0$,$a_1$ with integer coefficients? i.e. there exists two integers $i_0,i_1 \in \Bbb Z$ ...
1
vote
2answers
32 views

Given a sequence $a_1,a_2,\ldots ,a_n$, if $\gcd(a_1,a_2,\ldots ,a_n) = 1$, then there exists one pair $a_i,a_j$ st. $\gcd(a_i,a_j)=1$.

Anyone can help prove the following claim using elementary proof (no advanced number theory stuff)? Given a sequence $a_1,a_2,\ldots,a_n$, if $\gcd(a_1,a_2,\ldots,a_n) = 1$, then there exists at ...
2
votes
0answers
68 views

Cardinality of set of fractional sums

What is the cardinality of the set $S_2$: $$ \frac{1}{a_1^n} + \frac{1}{a_2^n}, 1 \leq a_1,a_2 \leq k \in N$$ for different values of $n$? I suspect there is an $n_0$ for which $|S_2| = ...
0
votes
0answers
20 views

dirichilet class number and non-vanish of L function at s = 1

All: I have been confused by dirichilet class number formula. We know that L ( 1 , χ ) is related to the class number h(d) with a constant. And this is one way that we can prove ...
0
votes
1answer
30 views

Let $m$ be the number of solutions of the equation $x^2 = 1$ in the ring $Z_n$, where $Φ_n$ is Euler group, $n> 2$.

Let $m$ be the number of solutions of the equation $x^2 = 1$ in the ring $Z_n$, where $Φ_n$ is Euler group, $n> 2$. Prove that $m$ is an even number. Could anyone help me or give me a hint? ...
3
votes
4answers
147 views

Find the last $4$ digits of $2016^{2016}$

Find the last $4$ digits of $2016^{2016}$. Technically I was able to solve this question by I used Wolfram Alpha and modular arithmetic so the worst I had to do was raise a $4$ digit number to ...
0
votes
3answers
36 views

Solve for $A,B$: $\mathrm{LCM}(A,B)=168$, $\mathrm{HCF(A,B)}=12$

The highest common factor and the lowest common multiple of two numbers $A$ and $B$ are $12$ and $168$ respectively. Find the possible values of $A$ and $B$ with the exception of $12$ and $168$. ...
1
vote
1answer
24 views

Show that if $(x,y,z)$ is a Pythagorean triple then $(x,y,z) = ({u^2-v^2 \over 2},uv,{u^2 + v^2 \over 2})$ for odd $u,v \in \mathbb{Z}$

I've encountered the following problem: Let $(x,y,z)$ be a Pythagorean triple of positive integers such that $gcd(x,y)=gcd(x,z)=gcd(z,y)=1$, and y is odd. Prove that there exists $u>v>0$ ...
0
votes
0answers
21 views

Definition of real by infinite series instead of their Cauchy limits

Looking at Wikipedia´s definition of real numbers I choose a variant one of the alternative definitions, using Cauchy limits. However, Instead of taking a limit I choose the number to be represented ...
2
votes
3answers
55 views

Find all $x \in \mathbb{N}$ that satisfy $pφ(x)=x$, where $p$ is a prime.

Find all $x \in \mathbb{N}$ that satisfy $pφ(x)=x$, where $p$ is a prime. This is a generalization of Solve the equation $2φ(x)=x $ for $x\in\mathbb N^+.$, where this is solved for $p=2$. My ...
1
vote
1answer
70 views

To show that a given number is prime

Show that $1010101...01$, where there are $2016$ zeros, is a prime number. The number alternates between $1$'s and $0$'s and ends in a $1$. The total number of zeros showing up is $2016$. Now this ...
1
vote
2answers
69 views

Solve the equation $2φ(x)=x $ for $x\in\mathbb N^+.$ [duplicate]

Solve the equation $2φ(x)=x $ for $x\in\mathbb N^+.$ I know $$x=\prod_\limits{i} p_i^{a_1} =p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3} \ldots p_n^{a_n}$$ ...
0
votes
1answer
39 views

Show that if the gcd of a set of non-negative integers $n_1,n_2,…,n_k$ is 1, then there exists $c_1,…,c_k\in\Bbb Z$ st. $\sum_{i=1}^k c_in_i=1$

Show that if the gcd of a set of non-negative integers $n_1,n_2,...,n_k$ is 1, then there exists $c_1,c_2,...,c_k\in\Bbb Z$ st. $c_1n_1+c_2n_2+...+c_kn_k=1$. Anyone can help give a understandable ...
0
votes
0answers
27 views

find an example of integers $0 < v < u$ that do not have a common factor, yet the pythagoran triple…

find an example of integers $0 < u < v$ that do not have a common factor, yet the pythagoran triple $(u^2-v^2, 2uv, v^2 + u^2)$ is not primitive. Before any major assistance I am just tryimg to ...
0
votes
3answers
89 views

Showing that the series $\sum \log{n}/n^2$ converges.

I aim to show that the series $$\sum \frac{\log{n}}{n^2}$$ converges. I know that the inequality $log(n) < \sqrt{n}$ holds for large $n$. So this give us one way to prove the convergence of $\sum ...
0
votes
1answer
25 views

Mult inverse in $\Bbb Z_{26}$

I tried doing a problem for finding $7$ inverse in $\mathbb Z_{26}$ I just want to know if my answer of $15$ is correct. I applied Euclid`s extended theorem and then did back substitution. My ...