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

learn more… | top users | synonyms (1)

0
votes
3answers
49 views

Find the sum of all $x$, $1 \le x \le 100$, such that $7$ divides $x^2+15x+1$.

Find the sum of all $x$, $1 \le x \le 100$, such that $7$ divides $x^2+15x+1$. I am clueless about how to approach this problem. Trying some values of $x$ I've found $2,4,9,11,16$ to satisfy ...
0
votes
0answers
44 views

Finding cardinality of a set which sum of its elements equal to an integer

Let $A_m$ be a set such that $$ A_m = \left\{(a_1,a_2,\ldots, a_n)\in \mathbb{N}^n |\, a_1 + a_2 + \ldots + a_n = m \right\} $$ Can we calculate cardinality of $A_m$, i.e Card(A_m) = |A_m| = ? Thank ...
0
votes
0answers
40 views

Show that the integers $a$ and $b$ can be chosen such that $ ha-kb=1$ holds for any given integers $h$ and $k$

During a longer calculation I encountered a problem where I need to show that one can pick two integers $a$ and $b$ such that $ha-kb=1$. Here $h$ and $k$ are two given integers. We have to assume ...
1
vote
1answer
25 views

Sequence of remainders of multiples

I am interested in the sequence of remainders of the integers $kp$ when divided by $q$, with $\gcd(p,q)=1$. For instance, with $p=7,q=17$, ...
5
votes
2answers
141 views

If $a^4 + 4^b$ is prime, then $a$ is odd and $b$ is even.

We say an integer $p>1$ is prime when its only positive divisors are $1$ and $p$. Let $a$ and $b$ be natural number not both $1$. Prove that if $a^4+4^b$ is prime, then $a$ is odd and $b$ is even. ...
-2
votes
2answers
79 views

Is $0$ stands for “nothing” or “none” [closed]

If the answer is yes how one can say $-1 < 0$, i.e how "something" can be smaller than "nothing"? If the answer is no, how $0$ is defined in mathematics?
0
votes
2answers
49 views

Congruence for large modulus

The idea it to find remainder $35^{32} + 51^{24} \bmod 1785$. 1785 is a composite number equal to 3 x 5 x 7 x 17. 35 is 0 mod 5 and mod 7. 51 is 0 mod 3 and mod 17. Any help regarding steps from ...
1
vote
1answer
58 views

Elementary proof of the prime number theorem?

The prime number theorem is equivalent to $\lim_{x \to \infty} \dfrac{1}{x} \left| \sum_{n\leq x} \mu(n) \right| = 0$, where $\mu(n)$ is the Mobius function. We know that $\left| \sum_{n\leq x} ...
2
votes
4answers
80 views

Why does division by zero not have an imaginary number “option”? [duplicate]

In regular math, you cannot get the square root of a negative number. Likewise, you cannot divide by zero. Both dividing by zero and taking the square of a negative have no place in real life. ...
3
votes
1answer
35 views

Diophantine equation with $gcd = 1$

John has $100$ marbles and wants to split them into $4$ groups $A,B,C,$ and $D$ such that the greatest common divisor of the number of marbles in all of the groups is $1$. Find the number of ways ...
1
vote
1answer
23 views

On Mersenne composite numbers (need of a proof).

On the Wikipedia page on Mersenne primes it says If $n$ is a composite number then so is $2^n − 1$. ($2^{ab} − 1$ is divisible by both $2^a − 1$ and $2^b − 1$.) The part inside the brackets ...
2
votes
1answer
33 views

Diamond Numbers and Fermat's method of Factorization

I call numbers which are the product of two consecutive numbers $n(n+1)$ "diamond numbers". Can they be used in factorizing numbers using Fermat's method of the difference of two squares,considering ...
0
votes
2answers
64 views

Solve the following number theory problem with 2 variables [closed]

Let there be $$a,b∈ \Bbb Z$$ Demonstrate that there exist no solutions for the following equation $$a^2-3b^2=-1$$
0
votes
3answers
42 views

$\operatorname{gcd} \, (a,b) = 1$ then $\operatorname{gcd} \, (a^n,b^k) = 1$

Statement: Suppose $(a,b) = 1$ then $(a^n,b^k) = 1$ for $n,k \geq 1$. Attempt at Proof: Let $P$ be the set of all primes. Let $P_a$ be the set of primes $p_i$ such that $$a = \prod_{i=1}^{r_1} ...
1
vote
2answers
45 views

Primality test for $n$

Assume $a,n\in\mathbb{N}$ such that $\gcd{(a,n)}=1$. We say $n$ is prime if $a^{n-1}\equiv 1\mod{n}$ and $a^x\not\equiv1\mod{n}$ for any divisor $x$ of $n-1$. I am presented with the following ...
0
votes
5answers
74 views

Prove that if $n^2 -2n +2$ is odd then $n$ is odd

Prove that if $n^2 -2n +2$ is odd then $n$ is odd I was wondering if you would prove this by using proof by contrapostive. I tried using proof by contrapostive, but I end up with the wrong ...
-4
votes
0answers
25 views

Numbers with 12 divisors

Find the positive integers $n$ with exactly $12$ divisors $1 = d_1 < d_2 < ... < d_{12} = n$ such that the divisor with index $d_4(ie, d_{d_4} - 1)$ is $(d_1 + d_2+ d_4)d_8$.
2
votes
2answers
44 views

Euler function formula

Given that $e\ge1$ and $p$ is prime. Prove that $$\varphi\left(p^e\right) = p^e\left(1-\frac1p\right)$$ We pick some $a\in\{0,1,\ldots,p^e-1\}$ which may be written as ...
1
vote
1answer
78 views

Is there any prime in the form of $10^n+1$ for $n>2$?

Is there any prime in the form of $10^n+1$ for $n>2$ ? It can be seen that $n$ is the form of $2^k$ so that this number is prime.
6
votes
3answers
56 views

Integers represented by $x^2 + 3 y^2$ vs. integers represented by $x^2 + x y + y^2$.

How does one show that the quadratic forms $x^2 + 3 y^2$ and $x^2 + x y + y^2$ represent the same set of integers? I think it relates to a classical result of Euler about primes of form $6k+1$. In ...
0
votes
1answer
51 views

Passing the fermat test

Let $p$ be a prime and $b\in\mathbb{Z}$ where ${\rm gcd}(b,~p)=1$. Prove that $b$ passes the Fermat test test for $m=p^2$ if and only if $b^{p-1}\equiv1$ mod $p^2$. We show this is true in both ...
1
vote
1answer
26 views

Determine the following property

For an integer $k \geq 3$, determine all sets $A=\{a1,...,a_k\}$ of positive integers that have the following property: Whenever h,i,j are distinct then each of $a_h,a_i,a_j$ divides $a_h+a_i+a_j$.
1
vote
1answer
60 views

An equation in $\mathbb Z[x]$

Let $$p(x)=a_nx^n+a_{n-1}x^{n-1}+……+a_2x^2+a_0;\space\space (a_1=0)$$ be a polynomial in $\mathbb Z[x]$; let $\mathcal S$ the set of all such polynomials. It is considered the equation ...
7
votes
2answers
277 views

Finding the first digit of $2^{74207281}-1$ (new biggest prime record)

I heard that the record for finding the largest prime number was broken a few days ago with the following Mersenne prime $$2^{74207281}-1$$ also called $M_{74207281}$. Now my question is: it is ...
1
vote
3answers
40 views

Disprove bijection between reals and naturals

Coming across diagonalization, I was thinking of other methods to disprove the existence of a bijection between reals and naturals. Can any method that shows that a completely new number is created ...
0
votes
2answers
42 views

How many integers less than 2015 are multiples of 2 or 3 (or both)?

Here is what I did. To find all the multiples of 2 that is less than 2015 all we need to do is divide by 2. The same can be done for multiples of 3 that is less than 2015: 2015 / 2 = 1007 ...
1
vote
1answer
73 views

Is there a fixed integer $n$ for which ${\pi}^{n}$ is prime number?

I would like to know the relationship between $\pi$ and prime numbers distribution ,then I would like to ask if there is a fixed integer for which ${\pi}^{n}$ can be prime or how do i disproof that ...
-1
votes
0answers
16 views

Is there a closed form of $n$ for :$h(n)=\frac{\sigma(n)}{n}$ for which $n$ is coprime to $\sigma(n)$?

It is well known that $h(n)=\frac{\sigma(n)}{n}$ is quit irrigulrar,I'm very interesting to know more about it's behavior and i would like to know more about coprimality characteristic then it must be ...
9
votes
6answers
215 views

Which of the numbers $300!$ and $100^{300}$ is greater

Determine which of the two numbers $300!$ and $100^{300}$ is greater. My attempt:Since numbers starting from $100$ to $300$ are all greater than $100$. But am not able to justify for numbers between ...
27
votes
10answers
5k views

How to prove that all odd powers of two add one are multiples of three

For example \begin{align} 2^5 + 1 &= 33\\ 2^{11} + 1 &= 2049\ \text{(dividing by $3$ gives $683$)} \end{align} I know that $2^{61}- 1$ is a prime number, but how do I prove that ...
1
vote
5answers
102 views

The equation $a^3 + b^3 = c^2$ has solution $(a, b, c) = (2,2,4)$.

The equation $a^3 + b^3 = c^2$ has solution $(a, b, c) = (2,2,4).$ Find 3 more solutions in positige integers. [hint. look for solutions of the form $(a,b,c) = (xz, yz, z^2)$ Attempt: So I ...
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
22 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
42 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 ...