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

learn more… | top users | synonyms (1)

0
votes
1answer
20 views

Does there exist a finite set of homogeneous polynomials (+ property) whose unique solution is equivalent to a finite sequence of naturals?

Consider the set $\{2,3,5\}$ of natural numbers. Letting $p = 2, q = 3, r = 5$ we have: the polynomial equations: $$p + q = r, \\ p^2 + r = q^2 \\ q^3 - p = r^2 $$ Each is a homogeneous ...
4
votes
2answers
51 views

In the $x + 1$ problem, does every positive integer $x$ eventually reach $1$?

I know that the more famous $3x + 1$ problem is still unresolved. But it seems to me like the similar $x + 1$ problem, with the function $$f(x) = \begin{cases} x/2 & \text{if } x \equiv 0 ...
0
votes
0answers
21 views

Lower bound for $\Pi(n)$ - viability of probabilistic theory

Can somebody check the validity of my arguments below, and tell me why its wrong or right? Consider the sequence of non-negative integers. Let $a_0=0, a_1=1, ..., a_i=i,...$ Divisiblilty of $a_i$ ...
1
vote
1answer
28 views

Find all primes $p$ for which $x^2+2x+4\equiv 0 \pmod p$ is solvable. Am I correct?

Getting ready for an exam, I would like to focus on the correctness of my solution, final results and assumptions, and would appreciate any comment regarding it or even additional ...
0
votes
0answers
18 views

The distribution of prime and semi-prime.

Let $\alpha$ be an integer and $\rho_1,\rho_2$ some prime such that $\alpha=\rho_1\cdot\rho_2+1$, and $\beta$ the number of all semi-prime less than or equal to $\alpha$. Prove ...
1
vote
2answers
28 views

Proving that $a^{b}$ is rational (Elementary number theorey) [duplicate]

Prove that there exist irrational numbers $a$ and $b$ such that $a^{b}$ is rational. What i tried Prove by contradiction I assume the statement For all rational numbers $a$ and $b$ such that ...
0
votes
0answers
25 views

Showing $pk+1|p^p-1$ implies that $k$ is even

Suppose $p$ is an odd prime such that $pk+1$ divides $p^p-1$. Prove that it is not possible for $k$ to be odd. Here's my solution: Assume to the contrary that $pk+1$ does divide $p^p-1$ We can ...
2
votes
0answers
28 views

$a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $.

Let $n \in Z$, $n > 1$ and let $a \in Z$ with $1 \leq a \leq n$. Prove that if $a$ and $n$ are relatively prime then there exists an integer $k$ such that $ak \equiv 1(\mod n) $. Proof: Suppose ...
1
vote
1answer
23 views

Dirichlet theorem

Can anyone give a simple number theory proof for the Dirichlet theorem? Statement of Dirichlet theorem:given any two numbers a and b whose g.c.d is 1,Prove that infinitely many primes exist in the ...
3
votes
2answers
59 views

Prove that for every natural number $n > 2$ there is a prime number between $n$ and $n!$

So I have already read this page with the solution: For all $n>2$ there exists a prime number between $n$ and $ n!$ Now I was able to reason that $p < n!$ Because I was given the hint that ...
3
votes
2answers
111 views

Perfect numbers

Define a Perfect (capital-P) number as a natural number that is equal to the sum of its Divisors excluding 1 and the number itself. (So the Divisors of 28 are 2, 4, 7, 14, summing to 27.) Is there any ...
2
votes
1answer
62 views

Difficult sets of Equations, counting

Let $ m$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2009$, and let $ n$ be the number of solutions in positive integers to the equation $ 4x+3y+2z=2000$. Find the ...
0
votes
0answers
21 views

Is this an Alternate proof of the Uniqueness of Remainder Th.?

$\mathbf{Theorem}: \forall$ pairs of integers $(a,b)$, $\exists$ unique integers $q, r$ such that $a=bq+r$ and $0\le r \lt |b|$ Assuming that the existence of the integers $q,r$ is already proven, ...
0
votes
1answer
27 views

If $n=x^2+3y^2$ then any prime in $n$'s factorization is of an even power.

If $n=x^2+3y^2$ then any prime $p$ such that $p\equiv 2 \pmod 3$ in $n$'s factorization is of an even power. I have been spending hours trying to solve this because of some some issues withholding any ...
5
votes
1answer
52 views

Missing values of the ratio $\frac{(x+y+z)^2}{x^2+y^2+z^2}$

Let $x,y,z$ be some positive integers. Is it true that we cannot find any positive integer $n$ for which $$ \frac{(x+y+z)^2}{x^2+y^2+z^2}=1+\frac{2}{3n}\,\,? $$
2
votes
0answers
19 views

Smallest number of workers in factory, Diophantine approximation

Q. In a factory, the percentage of male workers was $53.7802\%$ (rounding to nearest fourth decimal place) last year. What is the smallest number of female workers working there? Hint: Diophantine ...
2
votes
1answer
31 views

$(a^{2^n}+1,a^{2^m}+1)=1 or 2$ [duplicate]

Prove that if $m\not =n,a$ are positive integers then $(a^{2^n}+1,a^{2^m}+1)$ is $1$ if $a$ is even and $2$ if $a$ is odd. I solve the problem in the following way: I assume that $m>n$ then ...
4
votes
1answer
54 views

Is every sufficiently large even integer the sum of distinct primes?

Is every sufficiently large even integer the sum of (any number of) distinct primes? No doubt this question has been asked before; does the conjecture/theorem have a name? It is related to ...
1
vote
1answer
66 views

Integer solutions to $ab=a+b$

If $ab=a+b$ is there only one possible solution,i.e. $a=b=2$? ($a$ and $b$ not equal to zero and are integers). If not what are the others? I have proved that $a$ always needs to be equal to $b$. My ...
5
votes
0answers
36 views

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have?

A natural number has exactly 10 divisors including 1 and itself.How many distinct prime factors can this natural number have? options given: (a) either $1$ or $2$ (b)$1$ or $3$ (c)either $2$ or ...
3
votes
2answers
508 views

A number n is not a Prime no and lies between 1 to 301,how many such numbers are there which is not divisible by 2,3,5,7.

A number n is not a prime and lies between $1$ and $301$, how many such numbers are there which are not divisible by $2$, $3$, $5$, $7$? a) $6$ b) $8$ c) $10$ d) $12$ My approach: ...
2
votes
2answers
39 views

If $\gcd(ab,c)=d$ and $c|ab$ then $c=d$

For all positive integers $a$, $b$, $c$ and $d$, if $\gcd(ab, c) = d$ and $c | ab$, then $c = d$. Need help proving this question, I know that $abx + cy = d$ for integers $x,y$ and that $c|ab$ can be ...
0
votes
1answer
50 views

Property for the natural numbers.

This question is inspired by another question I had, where I wanted to prove something about the natural numbers. Often in analysis books I see some proofs, where they use the natural numbers, but it ...
0
votes
1answer
16 views

$f_n(x) = \left\lfloor \frac{\sin(2\pi (x / n + 1/ 4) + 1 }{2}\right\rfloor$ and related

$f_n(x) = \left\lfloor \frac{ \sin(2\pi (\frac{x}{n} + \frac{1}{4})) + 1}{2}\right \rfloor = 1 \iff x = kn$ and $ f_n(x) = 0 \iff x \neq kn$. Let $g_n(x)$ be what's within the floor brackets. Then ...
0
votes
2answers
76 views

How many pairs $(m, n)$ exist?

For certain pairs $ (m,n)$ of positive integers with $ m\ge n$ there are exactly $ 50$ distinct positive integers $ k$ such that $ |\log m - \log k| < \log n$. Find the sum of all possible ...
1
vote
1answer
35 views

For every natural integer $N>3$ there are at least two distinct prime numbers $p$ and $q$ such that $\dfrac{p+q}{2}=N$ and $N-p=q-N$, $(p<q)$.

I'm not sure but this problem may be similar or related to Goldbach conjecture? Any proof/disproof, insight and opinion is appreciated, thanks.
4
votes
1answer
35 views

Is it impossible to recover multiplication from the division lattice categorically?

In this question it was asked if the division lattice (i.e., the preorder category $(\Bbb Z_{>0}, \mid)$) contains enough information categorically to recover the relation ...
5
votes
0answers
45 views

Integers which are the sum of non-zero squares

Lagrange's four-square theorem states that every natural number can be written as the sum of four squares, allowing for zeros in the sum (e.g. $6=2^2+1^2+1^2+0^2$). Is there a similar result in which ...
3
votes
2answers
80 views

New deterministic primality test for numbers of the form $p\cdot 2^n + 1$

Edit: Sorry, there was an error. Old Claim (not true because there is a counter-example): Let $p$ be prime. Let $n \in \left\{1, 2, 3, ...\right\}$. Then $N = p\cdot 2^n+1$ is prime, if and only ...
4
votes
1answer
60 views

Each number in $S\subseteq \{1,\ldots,2n\}$ does not divide another one, with $|S|= n$. In how many ways?

Let $f(n)$ be the number of subsets $S\subseteq \{1,2,\ldots,2n\}$ such that $|S|=n$ and $a$ does not divide $b$ whenever $a,b \in S$ are distinct. Can we evaluate $f(n)$, at least asimptotically? ...
3
votes
2answers
70 views

Question about irrationality proof of $\sqrt{n}$

I'm talking specifically about a proof that I've found. I don't seem to get some parts of it. It states that if you take: $$\sqrt{n}=\frac{p}{q} \:\: \;\;p,q \in \mathbb{Z} $$ where $p$ and $q$ share ...
0
votes
0answers
17 views

Composition of polynomial and multiplicative is multiplicative .

I made the following problem a while ago but I can't solve it (also I don't think it's extremely hard ) : Let $f$ be a non-constant completely multiplicative function over $\mathbb{Z}$ . Assume ...
0
votes
1answer
19 views

What am I doing wrong here? Showing $\text{Ord}_{N}(a)|k\iff a^k\equiv 1 \pmod N$.

Show $\text{Ord}_{N}(a)|k\iff a^k\equiv 1 \pmod N$ where $a$ is invertible. What I did is: If $\text{Ord}_{N}(a)|k$ it is obvious. Suppose $a^k\equiv 1 \pmod N$. Not let us assume by contradiction ...
-1
votes
1answer
12 views

What place value rounded would be the closest answer to the difference between 62960 and 49605 [on hold]

What place value rounded, ten thousands, thousands or hundreds would be the closest answer to the difference between 62960 and 49605
2
votes
2answers
25 views

The number of ordered pairs of positive integers $(a,b)$ such that LCM of a and b is $2^{3}5^{7}11^{13}$

I started by taking two numbers such as $2^{2}5^{7}11^{13}$ and $2^{3}5^{7}11^{13}$. The LCM of those two numbers is $2^{3}5^{7}11^{13}$. Similarly, If I take two numbers like ...
2
votes
1answer
34 views

exercise Question-29 from contemporary abstract algebra [on hold]

Consider the element A=(1101) in SL(2,R) what is the order of A? If we view A=(1101) as a member of SL (2,Zp), what is the order of A
0
votes
1answer
26 views

Continuous functions with domain in the Natural Numbers

Can functions with domain in the Natural Numbers be continuous? In the high school, it is teached an intuitive notion of continuous functions: functions which will always appear as an "unbroken ...
6
votes
1answer
66 views

If $a^{n}-1$ is divisible by $n$, then $a+1,a^2+2, \ldots a^n+n$ leave different remainders when divided by $n$

It is given that $a^n-1$ is divisible by $n$ for some natural numbers $a$ and $n$. Prove that the numbers $$a+1,a^2+2, \ldots a^n+n$$ all leave different remainders when divided by $n$. I tried ...
0
votes
1answer
15 views

How many ways are there to express a natural as a sum of 3 others—but by induction?

I have figured out an (inductive?) process, but I cannot express it formally: There is always one possibility where $n$ is in the first place of our 3-tuple: $[n~~0~~0]$. Then I can subtract $k~(\leq ...
0
votes
1answer
21 views

An equation of three variables has integral solution

The given equation is $63x+70y+15z=2010$ and I have to whether it has any integral solution and if yes what that is . Now this is one equation in $3$ variables . How can ...
3
votes
1answer
66 views

Each number in a subset $S\subseteq \{1,\ldots,2n\}$ does not divide another one. Then $\max |S|$?

This problem comes from a seemingly innocuous question from a professor during a lesson for a Math Olympiad course. [A part of this question is really a classic of number theory/combinatorics] ...
1
vote
4answers
178 views

Find the least positive residue of $10^{515}\pmod 7$. [on hold]

I tried it, but being a big number unable to calculate it.
0
votes
3answers
49 views

Solve the congruence $31x\equiv 5 \pmod{23}$

I've used the Euclidean Algorithm to solve congruences of the form $$ax \equiv b \pmod n$$ where $n >a$, for example: $16x \equiv 5 \pmod{29}$. When $n <a$, for example, $$31x \equiv 5 ...
1
vote
2answers
32 views

For a natural number b, N(b)= number of natural numbers a such that the equation x2+ax+b=0 has integral roots.

For a natural number $b$, $N(b)= $ number of natural numbers $a$ such that the equation $x^2+ax+b=0$ has integral roots. What is the lowest possible value of $N(6)$?
3
votes
0answers
59 views

Connections between Fibonacci and natural numbers

Here are some known facts about Fibonacci numbers and then some questions regarding them . 1.Carmichael's theorem . For every $n>12$ $F_n$ has a prime divisor which doesn't divide any of the ...
3
votes
3answers
72 views

Prove that $\sqrt{3}$ is not a rational number [duplicate]

There is a similar question however that question asks why $3 |p^2$. Here the question is about $ 3 | p^2 \rightarrow 3 | p$. It is a simple exercise (1.2.1) from Abbot's "Understanding Analysis". ...
1
vote
0answers
37 views

Does the “alternating” harmonic series where only prime terms are negative converge?

We know that the harmonic series $\sum \frac{1}{n}$ diverges, yet the alternating harmonic series $\sum \frac{(-1)^n}{n}$ converges. Euler famously gave a proof of the infinitude (and of the ...
0
votes
2answers
70 views

$f:\mathbb{N}\rightarrow \mathbb{N}$ is a one-to-one function such that $f(mn)=f(m)f(n).$ Find the lowest possible value of $f(999)$. [duplicate]

$f:\mathbb{N}\rightarrow \mathbb{N}$ is a one-to-one function such that $f(mn)=f(m)f(n).$ Find the lowest possible value of $f(999)$. The answer is given as $24$ but I never get that.
4
votes
2answers
97 views

Consecutive sets of consecutive numbers which add to the same total

I'm looking at examples of numbers that can be written as the sum of integers from $j$ to $k$ and from $k+1$ to $l$. For example $15$ which can be written as $4+5+6$ or $7+8$. Or $27 = 2+3+4+5+6+7 = ...
-3
votes
0answers
44 views

If $p$, $q$, and $r$ are all odd primes, which of $p^2-q^2+1$, $pqr+3$, and $(p+2)(r+2)+1$ can be prime? [on hold]

If $p$, $q$, and $r$ are all odd primes, which of the following might also be a prime? a) $p^2-q^2+1$ b) $pqr+3$ c) $(p+2)(r+2)+1$