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

learn more… | top users | synonyms (1)

2
votes
2answers
32 views

Using a sieve and Mertens' theorem to show a formula for $\pi(x)$ - Does this work?

When I was younger, just starting highschool, I loved tinkering with prime sieves. I still have notes that I took. I had written down that $$\pi(x)\sim x\prod_{n=1}^m\frac{p_n-1}{p_n}+m-1.$$ ...
7
votes
1answer
81 views

Is the set $\phi(\mathbb{N})$ syndetic?

A set $A \subset \mathbb{N}$ is said to be syndetic if the gaps in $A$ are bounded. Is the set $\phi(\mathbb{N})$ syndetic? (where $\phi$ denotes de Euler totient function) I've thought quite a ...
2
votes
1answer
25 views

Is there a necessary form of consecutive composites?

For every $n \geq 3$ there is a tuple of $n-1$ consecutive composites, namely the composites of the form $n! + 2, \dots, n!+n$. However, must a tuple of $n$ consecutive composites take the form? It ...
-1
votes
0answers
29 views

Values of the Sudan function

I am talking about the first discovered recursive function which is not primitive recursive. I would like to know the exact values of $\ f(3,3,3), f(2,0,4), f(2,7,1), f(2,3,2)$ (where $f$ is the ...
1
vote
0answers
39 views

Possible maps $(\mathbb Z[i]/\mathfrak p)^\times\to\mu_4$

Let $\mathfrak p$ be a maximal ideal of $\mathbb Z[i]$ not dividing 2. Is it true that the only maps from the cyclic group $(\mathbb Z[i]/\mathfrak p)^\times$ the the fourth roots of unity are powers ...
0
votes
1answer
28 views

Proof of decimal expansion [duplicate]

If the denominator of a rational number contains only 2 and 5 as prime factors then the decimal expansion of the rational number is terminating. How can I Prove this
4
votes
1answer
209 views

How do I prove that there is no other :$k=9,12,18$ for which this fails :$\sigma^k(114) \equiv 0\mod 6 $?

let $\sigma(n)$ be the sum of divisors for a positive integer for example : $$\sigma(6)=1+2+3+6=12$$ . I have performed some calculations in wolfram alpha about the sum divisors of this number: ...
0
votes
0answers
18 views

Determining recurring decimal expansion

Is it possible to determine if the decimal expansion of a rational number is recurring or terminating by looking at the denominator, without actual division
0
votes
2answers
34 views

Showing that these two definitions of $\gcd(a,b)$ are equivalent

So far I have encountered with two definitions of the GCD of $a$ and $b$. The first definition is: $\gcd(a,b)$ is an integer that has the following properties: $d>0$ $d\mid a$ and ...
0
votes
0answers
30 views

Number Theory by Andreescu and Andrica Problem 1.6.2 Solution

Problem 1.6.2 in Number Theory by Andreescu and Andrica is taken from 1997 Czech and Slovak Mathematical Olympiad, and is stated as follows: "Show that there exists an increasing sequence $\{a_n\}$ ...
0
votes
1answer
34 views

What is the probability of occurence of natural numbers?

Suppose that humankind had a ∞-ary number system so that no psychologically distinguished numbers like 1000, 250, or 333 existed. What is the probability of a number n ∈ ℕ (including 0) to occur when ...
1
vote
0answers
80 views

Taking partial sums repeatedly to get to perfect powers.

Let $S_{1,k}(n) = n,\ S_{i,k}(n) = \sum_{\text{n terms},(k-i+2)\nmid j} S_{i-1,k}(j)$ For example, $S_{1,2}(n) = n, S_{2,2}(n) = 1 + 3 + \dots+(2n-1) = n^2$ With $k=3$, take partial sums avoiding ...
0
votes
1answer
20 views

Are these partial sums and partial products absolutely convergent?

For arbitrary $m \in \mathbb{N},$ $$\sum_{n=1}^{m}\ \sum_{d | \#_n}\mu(d)=\sum_{n=1}^{m}\big | \sum_{d | \#_n}\mu(d)\ \big |\ = \ 0,$$ $$\prod_{n=1}^{m}\ \prod_{d | \#_n}d^{\mu(d)}=\prod_{n=1}^{m}\big ...
2
votes
3answers
54 views

Change of radix without using radix 10

If one has a number in radix $b$: $(d_nd_{n-1}\ldots d_0)_b$, and wants to change to radix $p$, how could one achieve that without passing from $b$ to $10$ and then from $10$ to $p$? I thought I had ...
3
votes
1answer
52 views

Solve $2b(b-1) = t(t-1)$ as Pell's equation

I know the method of continued fractions to solve the Pell's equation. I need help turning $2b(b-1) = t(t-1)$, with $b, t$ as integers, into the form $x^2 - ny^2 = 1$, if possible. This is a Project ...
4
votes
2answers
69 views

If for almost all $p \equiv 1$ (mod a) it holds that $p \equiv 1$ (mod m), then…

Let $a,m\in \mathbb N$ Suppose that for almost all primes $p \equiv 1$ (mod a) we have that $p \equiv 1$ (mod m) Can we say something about $a$ and $m$? For example $m$ divides $a$ or vice versa? I ...
3
votes
3answers
51 views

Is this formula true for $n\geq 1$:$4^n+2 \equiv 0 \mod 6 $?

Is this formula true for $n\geq 1$:$$4^n+2 \equiv 0 \mod 6 $$. Note :I have tried for some values of $n\geq 1$ i think it's true such that :I used the sum digits of this number:$N=114$,$$1+1+4\equiv ...
6
votes
2answers
77 views

Existence of $\sqrt{-1}$ in $5$-adics, show resulting sum is convergent.

I know that to prove the existence of a square root of $-1$ in $\mathbb{Z}_5$, I can just plug $x = -5$ and $a = 1/2$ into the Taylor expansion$$(1 + x)^a = \sum_{n=0}^\infty \binom{a}{n} ...
3
votes
3answers
73 views

Arrangements of Chairs in a Circle

Ten chairs are arranged in a circle. Find the number of subsets of this set of chairs that contain at least three adjacent chairs. Hints only please! This is a confusing worded-problem. We ...
4
votes
4answers
61 views

Express 2104 as the sum of four squares

How to write 2104 as the sum of four squares. I know the general equation for factoring a number into the sum of four squares but I don't know how to go about this when some of the prime factors are ...
5
votes
0answers
43 views

Sequence involving floor function - limit and bounds

My first time here, so please excuse any breaches of etiquette. For a given $p \in \mathbb N$ and irrational $\alpha$, let $\varepsilon_n=\alpha n-\lfloor \alpha n \rfloor,$ and ...
3
votes
2answers
70 views

How to show that that the following three consecutive numbers $3^{2^{10}} − 1$, $3^{2^{10}}$,$3^{2^{10}}+ 1$ are the sum of two squares?

Show that the following three consecutive numbers: $$ 3^{2^{10}} − 1, 3^{2^{10}} , 3^{2^{10}} + 1 $$ can be represented as sums of two integer squares.
2
votes
1answer
122 views

Show that the equation $y^2 = x^3 + 3$ has infinitely many rational solutions in $x$ and $y$.

Show that the equation $y^2 = x^3 + 3$ has infinitely many rational solutions in $x$ and $y$. I'm really not sure how to go about this question. I've been using trial and error and have not got ...
1
vote
0answers
62 views
+50

Special Case of Composite mersenne number mod p

We want to investigate if a composite mersenne number $p|2^{qb}-1$ where $p\nmid2^q-1$ ,$q,p$ are primes, $p=1+6qb,\ qb\equiv1(mod64) $ and $b$ is an odd number. In general for $$\begin{align*} ...
0
votes
0answers
29 views

Looking for problems which can be solved by the similar technique

While browsing on internet for different proofs of Fermat's theorem on sums of two squares, I came across Zagier's "one-sentence proof" which seems to be the most elegant and short proof. It invokes a ...
0
votes
3answers
67 views

Calculate the exact value of the following expression [closed]

I propose the following exercise. Calculate the exact value of$$P=\dfrac{(10^{4}+324)(22^{4}+324)(34^{4}+324)(46^{4}+324)(58^{4}+324)}{(4^{4}+324)(16^{4}+324)(28^{4}+324)(40^{4}+324)(52^{4}+324)}$$ ...
5
votes
0answers
54 views

a new(?) operation using products of multiplicities

Does the operation $$n \odot m := \prod_{p \text{ prime}} p^{v_p(n) \cdot v_p(m)}$$ on positive integers have a common name? Has this operation been studied somewhere? Notice that $\odot$ is ...
2
votes
2answers
70 views

How can I simplify $123^{11} \mod 323$?

I am busy studying the RSA cryptosystem and would like to know how to simplify things like this: $123^{11} \mod 323$
4
votes
1answer
75 views

Does Euler's $\phi$ function have the same value in arbitrarily large subsets of $\mathbb{N}$?

As my most recent question still does not have any answers and it appears to be a difficult problem, I propose the following problem (that seems easier), but which I still could not manage to solve: ...
0
votes
3answers
25 views

Is there a simple way to simplify the congruence?

Is there a simple way to simplify the congruence? $25^{1203} \equiv 25^3 \pmod{23}$ without subtracting $23$ from $25^3$ a couple of times? In other words, I would like to rewrite it as: $25^{1203} ...
3
votes
1answer
18 views

How can I solve the linear congruence for x with the use of an inverse?

Consider, for example, the linear congruence: $56x \equiv 23 ($mod $93)$ if we know that the inverse of of $56$ modulo $93$ is $5$. Multiplying both sides by the inverse, $5$, we have: $280 x \equiv ...
0
votes
1answer
51 views

Use Fermat's little theorem to solve $7^{222}$mod $11$

The textbook gives the answer as: By Fermat’s little theorem, we know that $7^{10} ≡ 1 \pmod{11}$, and so $(7^{10})^k ≡ 1 \pmod{11}$, for every positive integer $k$. Therefore, $7^{222} = ...
1
vote
2answers
34 views

Comparison of two collections of 4-tuples using combinatorics - more complicated version

My problem is to show that 2 collections of unordered 4-tuples - $\mathbf{A}$ and $\mathbf{B}$ - are the same. I define a collection of objects as a set, in which multiple entries of the same object ...
1
vote
5answers
86 views

If $n = 4k + 1$, does $4$ divide $n^2 -1$?

How would I show that $4$ divides $n^2 -1$ if $n = 4k+1$? Is there more than one way to solve this?
-3
votes
1answer
47 views

Adding fractions in two ways - a paradox? [duplicate]

Adding 1/3 to 2/3 gives 1 EXACTLY. But expanding the two fractions and then adding gives 0.99999 Where is the flaw in this reasoning?
1
vote
2answers
56 views

Fourth power and least common multiple (urgent)

I have been given a mathematics test with the question* (we are allowed to use online resources): Find all positive answers for the following expression $$ x - y^4 = \def\LCM{{\rm lcm}}\LCM(x, y)$$ ...
1
vote
0answers
34 views

What are modulos and how would I be able to use them to solve questions regarding the last digit of a raised power?

When given questions like "What is the last digit of the result to 3^56?", I usually look for a recurring pattern involving smaller powers of 3. In this question for example, the recurring pattern for ...
3
votes
0answers
57 views

Is the set of integers so that $n!+1$ divides $(2012n)!$ finite or infinite?

I am having trouble with this problem. We have to determine whether the set of integers such that $n!+1$ divides $(2012n)!$ is finite or infinite. Basically we have to determine if the prime factors ...
2
votes
2answers
156 views

Divisibility question

Prove: (A) sum of two squares of two odd integers cannot be a perfect square (B) the product of four consecutive integers is $1$ less than a perfect square For (A) I let the two odd integers ...
1
vote
3answers
54 views

Find the number $ccbb$

If the number has $4$ digit $ccbb$ and it's full square, then find that number. I have tried and I got $88^2=7744$ but my way has no prove for it, if any one have away, I'll appreciate it.
-3
votes
3answers
66 views

Find the value of $x$ [closed]

Find the value of $x$, $$\left ( \frac{4}{\sqrt{3}-\sqrt{2}} \right )^{4-x}=\left ( 80+32\sqrt{6} \right )^{x}$$ any help?
2
votes
1answer
30 views

System of Congruences with Special Symmetry

Show that the following system of congruences \begin{align} \begin{cases} 3 x^4 - 7 x^2 y^2 - 7 x^2 z^2 - 35 y^2 z^2 \equiv 0 \pmod{p} \\ 3 y^4 - 7 x^2 y^2 - 7 y^2 z^2 - 35 x^2 z^2 \equiv 0 \pmod{p} ...
0
votes
3answers
155 views

Is infinity an element of the natural numbers? [duplicate]

I am wondering, whether $\infty \in \mathbb{N}$.
6
votes
2answers
313 views

Smallest Positive Integer Not Coprime to a Collection of Consecutive Integers

Let $n\in\mathbb{N}$. Define $f(n)$ to be the smallest positive integer $m$ such that there exists a positive integer $k$ for which $k+i$ is not relatively prime to $m$ for every ...
1
vote
2answers
40 views

Proving basic floor function inequality: $-1 \lt \lfloor 2x \rfloor - 2 \lfloor x \rfloor \lt 2$

As a direct consequence of the definition of $\lfloor x \rfloor $ I know that $$2x-1 \lt \lfloor 2x \rfloor \le 2x$$ and $$2x-2 \lt 2\lfloor x\rfloor \le 2x$$ How can I use these to show that $-1 \lt ...
1
vote
4answers
96 views

Find the value of $\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}$

If $$x+y+z=7$$ and $$\frac{1}{x+y}+\frac{1}{y+z}+\frac{1}{z+x}=\frac{7}{10}$$ Find the value of $$\frac{x}{y+z}+\frac{y}{z+x}+\frac{z}{x+y}$$ I tried but I got nothing
7
votes
0answers
127 views

Is the Euler function $\phi$ constant in arbitrarily large intervals?

Is it true that for every $k \in \mathbb{N}$ there exists a natural number $x$ such that $\phi(x)=\phi(x+1)=\cdots=\phi(x+k)$, where $\phi$ is the Euler's totient function? I thought about this ...
0
votes
1answer
36 views

Simple Linear Diophantine Equation - problem with proof.

I'm reading up on diophantine equations and one of the theorems is that "if $x,y$ is any solution of $ax + by = c$, then it is of the form $x_0 +\dfrac{b}{d}t ,\, y_0 - \dfrac{a}{d}t$ where $d = ...
1
vote
2answers
21 views

Distribution of decimal repunit primes

The prime number theorem describes the distribution of prime numbers in positive integers. Is there a similar theorem describing the distribution of primes among positive integers of the form ...
5
votes
2answers
71 views

Can $|m\alpha+n\beta|$ be made arbitrarily small?

I wondered is that always true that if $\alpha$ and $\beta$ are non-zero real numbers, then can we make $|m\alpha+n\beta|$ arbitrarily close to zero, for some non-zero integers $m$ and $n$. My guess ...