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

learn more… | top users | synonyms (1)

25
votes
6answers
2k views

Is it possible to describe the Collatz function in one formula?

This is related to Collatz sequence, which is that $$C(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 & \text{if } n\equiv 1 \pmod{2} .\end{cases}$$ Is it possible to describe ...
1
vote
1answer
29 views

Distribution of QRs mod p

$$ \sum_{a=1}^{p-1} (\frac{a}{p})a^n \equiv{0} \pmod{p} $$ I'm supposed to show this for $p \equiv 1 \pmod 4$ with $n=1$, and for $ p\gt 5$ with $n=2$. I already know the standard case of $n=0$. For ...
5
votes
1answer
81 views

Maximum amount of divisors of the number $n^m+m^n$

We are given some positive integer $m$. What maximum amount of distinct prime divisors a number $n^m+m^n$ can have, where $n\in\mathbb{Z}_+$? Edit: As noted in comments, there is no reason to think ...
3
votes
2answers
123 views

Length of digits before the period in decimal expansion for rational numbers

I'm a newbie with number theory and I've been reading this page and trying to figure out how to calculate the length of the digits before the period and digits of the period of a rational number of ...
2
votes
1answer
36 views

Prove $m_1m_2\ldots m_k$ and $m_{k + 1}$ are relatively prime.

If $m_1, m_2, \ldots, m_k, m_{k + 1}$ with $m_i > 0 \in \mathbb Z $ are pairwise relatively prime, then $m_1m_2\ldots m_k$ and $m_{k + 1}$ are relatively prime. Let $n = m_1m_2\ldots m_k$ and ...
2
votes
1answer
39 views

Given a prime number $p$, prove that there exists infinitely many prime number $q$ which is congruent with 1 by modulo $p$.

Can anybody help me to solve the problem as stated in the title: Given a prime number $p$, prove that there exists infinitely many prime number $q$ which is congruent with 1 by modulo $p$. I am ...
1
vote
1answer
54 views

Chinese Remainder Theorem: solving $x^2 \equiv 1$ (mod 91).

I am trying to solve the following problem: find all solutions to the congruence $x^2 \equiv 1$ (mod 91). Already, I have solved the congruence $x^2 \equiv 1$ (mod 7) and (mod 13) and I am trying to ...
2
votes
2answers
178 views

Is it true that the square of an even integer is always a multiple of 4?

Just out of curiosity. I'm new to number theory. If it's true, please show a proof. Thanks!
0
votes
1answer
62 views

Limit of sequence of irrational function

Are there any conditions or theorem to the limit of a sequence of irrational functions is irrational ? Please say something i don't know , because I already know sequences of examples of irrational ...
2
votes
2answers
48 views

Showing that a number is not divisible by another.

I am currently in a number theory class, but we don't have a textbook and even though I have been attending all the lectures we have not solved a problem similar to this in class. We have never proved ...
2
votes
2answers
71 views

Prove by induction $\sum \frac {1}{2^n} < 1$

Prove by induction $\sum \frac {1}{2^n} < 1$ Well supposing the base case has been shown to be true, I start with the induction step: Suppose true for n = k: $$ \frac{1}{2} + \frac{1}{4} + ...
3
votes
2answers
76 views

Calculate $3\cdot 4+ 4$ in $\mathbb{Z}_7$ and $\mathbb{Z}_{10}$.

Question: calculate $3\cdot 4+ 4$ in $\mathbb{Z}_7$ and $\mathbb{Z}_{10}$. I don't really understand how to approach this problem, any ideas are appreciated. Thanks.
0
votes
0answers
20 views

Irreducibility of a polynomial like $x^n-a$

Let $x^n-a \in F[x]$, where $F$ is field, be an irreducible polynomial on $F$, I want to prove: for any $m|n$, the polynomial $x^m-a$ is also irreducible on $F$. Any help is welcomed. Thanks all.
0
votes
1answer
15 views

if $a$ is a solution of any congruence modulo $p$, then $a + np$ also a solution for any $n$

Where does the statement in the title come from? I tried this below: $ya \equiv x \pmod p$ $p \mid ya - x$ $pq = ya - x$ $pq + ya = x$ Am I close?
0
votes
1answer
45 views

Show that $6x + 5 = 7 \pmod 5$ has infinitely many solutions.

Let $u$ be a solution to $6x + 5 = 7 \pmod 5$ so that $6u + 5 = 7 \pmod 5$. Then there's some $t$ such that $u = t \pmod 5$. Then $6u = t \pmod 5 \to 6u + 5 = t + 5 \pmod 5 \to 7 = t + 5 \pmod 5 \to ...
4
votes
1answer
186 views

Modulo polynomials, excluding selected solution combinations

Given $$ (x-a)(x-b)(x-c) \equiv 0\ \ \pmod {p} $$ $$ (x-d)(x-e)(x-f)\ \equiv 0\ \ \pmod {q} $$ x: unknown variable. p,q : known primes. a,b,c,d,e,f : known values. Are there one or more modulo ...
0
votes
2answers
29 views

Meaning of a vertical bar

So I've encountered something I haven't seen before. Could someone tell me what the following means: x | 5
3
votes
1answer
50 views

Are any zeros of Riemann zeta function and the zeros of the derivatives of Riemann zeta function same?

All: Are any zeros of Riemann zeta function and the zeros of the derivatives of Riemann zeta function same ? They shall be all different, right ? Is there a proof of this statement ? Thank you.
1
vote
1answer
11 views

Proving (for integers) that primality implies irreducibility

Let $Z = \{n \in \mathbb{Z} \; | \; |n| > 1\}$. Let $p\in Z$. $p$ is irreducible if for some $a,b \in \mathbb{Z}$: $$p = ab \implies |a| = 1 \vee |b| = 1$$ $p$ is prime if for $a,b \in ...
2
votes
2answers
28 views

Why is $1$ not an irreducible integer?

When defining irreducible integers, we restrict our attention $Z = \{n \in \mathbb{Z} \; | \; |n| > 1\}$. Then we say that for some $p \in Z$, $p$ is irreducible if for some $a,b \in \mathbb{Z}$: ...
0
votes
1answer
24 views

Proving the equivalent condition for primality

Let $p\in\mathbb{N}$, p>1 then p is a prime if and only if for every $a,b\in\mathbb{N}$, p=ab implies a=1 or b=1. if p=2, then a=1 and b=2, but if p=6, then a=2 and b=3 or a=1 and b=6. I ...
1
vote
1answer
30 views

Determine if $f(n) = n+k$ is completely multiplicative, multiplicative or neither.

Question Determine if $f(n) = n+k$ (k is a fixed real number) are completely multiplicative, multiplicative or neither. Attempted solution The only background I have at this point are (1) the ...
0
votes
0answers
13 views

Recover the value of N natural numbers from a set of M > N numbers

Take $N$ natural numbers, $n_1, \ldots, n_N$. Now, take $M > N$ functions $f_i: \mathbb{N}^N \rightarrow \mathbb{N}$. Now, given $n_1, \ldots, n_N$, I can compute $k_i = f_i(n_1, \ldots, n_N)$. ...
6
votes
4answers
417 views

Number of positive divisor

Given the following number "$11..11$" -$1992$ ones repeated-, prove that the number of positive divisor is even. I came up with the following idea: pick the number and rewrite the number this way: ...
3
votes
3answers
53 views

Let $a, n \in \mathbb{Z}_{\geq 0}.$ Prove that the product $(a+1) \cdots (a+n)$ is divisible by $n!$

Let $a, n \in \mathbb{Z}_{\geq 0}.$ Prove that the product $(a+1)\cdots(a+n)$ is divisible by $n!$. I think that can be done using the rule that ${a+n \choose n}= \dfrac {(a+n)!} {(a+n-n)! (n)!} $, ...
0
votes
1answer
24 views

If $6x + 5\equiv 7\pmod n$ has a solution, show that one of $1, 2, 3, \ldots, n - 1$ is also a solution

Let $u$ be a solution to $6x + 5\equiv 7\pmod n$ so that $6u + 5\equiv 7\pmod n$. So, there must be some $v$ such that $u \equiv v \pmod n.$ Then, $u \equiv v \pmod n \rightarrow 6u \equiv 6v \pmod n ...
1
vote
2answers
36 views

How to find the least common multiple

Does anyone has the method to find the least common multiple between $11$ and $28$? I've just started a course algebraic notion and I don't know how to use this powerful tool.
4
votes
5answers
71 views

Prove that for each number $n \in \mathbb N$ is the sum of numbers $n, n + 1, n + 2, …, 3n - 2$ equal to the second power of a natural number.

I've got a homework from maths: Prove that for each number $n \in \mathbb N$ is the sum of numbers $n, n + 1, n + 2, ..., 3n - 2$ equal to the second power of a natural number. I don't ...
0
votes
1answer
38 views

Find the Number of Solutions in $x^3 + y^3 + z^3 + w^3 = 0 \mod 5$

I at first interpreted the question as finding the number of incongruent solutions mod $5$ to the polynomial $x^3 + y^3 + z^3 + w^3 = 0$ exactly. As it turns out, we need to find the number of ...
1
vote
0answers
38 views

for every positive integer $k$, there exists an integer $x$ such that $kx^2-1$ is quadratic residue (mod $p$)

Prove that for every positive integer $k$, there exists an integer $x$ such that $kx^2-1$ is quadratic residue (mod $p$) I don't think this statement is true since $k$ the sequence $k \cdot ...
0
votes
0answers
25 views

How to know if addition of factorials changes the amount of trailing zeroes?

In this specific puzzle, it is $603!+604!+605!$. If it was $603!*604!*605!$ instead, I would simply count all the occurrences of multiples of 5, 25 and 125, which would be $148$ for $603!$ and ...
8
votes
2answers
330 views

How many pairs of positive integers (x,y) that satisfy equation $ x^2 - 10! = y^2$?

I have a question about number theory. How many pairs of positive integers $(x,y)$ that satisfy equation $$x^2 - 10! = y^2$$ ? My attempt: Move the $y^2$ from right to the left and 10! From left to ...
2
votes
2answers
88 views

Number Theory: Prove there are infinitely many primes $p$ satisfying $n\mid (p-1)$

I've been assigned the following problem for my homework: For any $n\in N$ show there are infinitely many primes $p$ satisfying $n\mid (p-1)$. I think I've proved it, but I'm uncertain since we were ...
1
vote
4answers
324 views

Let x and y be integers, prove that if 3 doesn't divide x and 3 doesn't divide y then 3 divides $x^2 - y^2$

Let x and y be integers, prove that if $3 \nmid x$ and $3 \nmid y$ then $3 \mid (x^2 - y^2)$ Attemmpt: The only thing i get out of this is that there is a difference of squares: $$(x^2 - y^2) = ...
2
votes
0answers
38 views

How many tubes can you balance in a centrifuge?

I recently learned that if you have a centrifuge whose number of holes $n$ is divisible by $6$, then you can balance any number of tubes except for $1$ and $n-1$. If $k$, the number of tubes you want ...
0
votes
1answer
28 views

How do we obtain that $(n|z|)^2-n|z|-1 \leq 0$?

I am looking at the following proof: Lemma. Let $n>1$. Suppose the following conditions $(9)$, $(10)$, $(11)$, and $(12)$ hold: $$(9) \ \ \ \ nz+nx-1 \mid_n n^2u-(nx-1)^2 \\ (10) \ \ \ \ ...
3
votes
1answer
39 views

Find $k \in \mathbb{N}$ such that $\frac{k^2}{(1+10^{-3})^k}$ is maximum.

The problem as in the title. What I tried so far: I investigated a function $f(x) = \frac{x^2}{(1+10^{-3})^x}$ for $x \geq 0$ So what I found out is that it's maximum is $x = \frac{2}{ln(1+10^{-3})}$ ...
2
votes
0answers
47 views

Where to find Brun's original combinatoric treatment of Brun Sieve?

I tried to understand Brun's original combinatoric treatment of Brun Sieve. (Unfortunately, I do not understand German), so I could not read Brun's original paper as in following: Viggo Brun (1915). ...
1
vote
1answer
54 views

Number of primitive characters modulo $m$.

Let $N(m)$ be the number of primitive Dirichlet characters modulo $m$. Could someone please explain me why it satisfies the following relation?: $$ \phi(m) = \sum_{d|m} N(m). $$ Thank you very ...
0
votes
0answers
28 views

What are some recursive properties of Merten function or Summatory Liouville function?

Both Merten function and Summatory Liouville function show some kinds of "scale invariance" properties. (Those functions also display some kind of "periodic" behavior.( Just wonder if those "scale ...
0
votes
0answers
26 views

What are equivalent statements or nature occurrences of Goldbach Conjecture in other math branches? [duplicate]

What are equivalent statements or nature occurrences of Goldbach Conjecture in other math branches ? We all know that Riemann Hypothesis(RH) has many (maybe over one hundred) equivalent statements. ...
2
votes
2answers
56 views

Friday the 13th future possible

A year normally has at most three Fridays the 13th. Year 2015 has three such days. What is the next year that has three Fridays the 13th again for the first time?
0
votes
1answer
38 views

All steps of finding a witness Rabin-Miller

Find a Rabin-Miller witness of compositeness of $n=49$ I have asked the same question before months but can we have a complete answer of how to find this witness? i mean with complete answer(all ...
0
votes
0answers
60 views

Random numbers on $[1, N]$

Let $n$ and $m$ be random numbers chosen independently and uniformly on $[1,N]$. What are $\Omega$, $A$ and $P$ (which all implicitly depend on $N$)? Prove that $P(n \land m = 1)$ as $N$ goes to ...
3
votes
4answers
461 views

If $a | b$, prove that $\gcd(a,b)$=$|a|$.

If $a | b$, prove that $\gcd(a,b)$=$|a|$. I tried to work backwards. If $\gcd(a,b)=|a|$, then I need to find integers $x$ and $y$ such that $|a|=xa+yb$. So if I set $x=1$ and $y=0$ (if $|a|=a$) ...
3
votes
1answer
64 views

Proving there are infinitely many different natural numbers such that $a^2+b \mid a+b^2$ [closed]

Prove that there are infinitely many different natural number so that $a^2+b \mid a+b^2$.
1
vote
1answer
27 views

Solving for an x value in modular arithematic. Efficient method exist?

Find a solution $x $ to the following congruence: $$2x \equiv 7 \pmod{11} $$. So my issue is not in solving this exact problem, I am more curious if there is a more efficient way of solving these ...
1
vote
2answers
42 views

Infinitely many even numbers that can be expressed as the sum of $m$ primes in $n$ different ways

Are there infinitely many even numbers that can be expressed as the sum of two primes in two different ways? If yes, are there infinitely many even numbers that can be expressed as the sum of two ...
1
vote
1answer
24 views

Predictability of consecutive powers

If $$a^b=c^d+1$$ $$a,b,c,d\in Z$$ $$a,b,c,d>0$$ then $a^b$ and $c^d$ are defined to be "consecutive powers" (atleast in my Q). Given two large positive integers $a$ and $b$, is it ...
1
vote
1answer
126 views

how do i know this without using calculator :$\sqrt{(9999²+19999)}$

I'm sorry to ask this question , I would like to know the value of this :$\sqrt{(9999²+19999)}$ without using calculator ? Note :I have used digit root theory but it's not work ? Thank you for any ...