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

learn more… | top users | synonyms (1)

0
votes
1answer
21 views

How to get initial digits from a sum before adding?

How would you add digits in such a way that when having a result sum, the initial digits that were added could be extracted/calculated? For example, when having the following random digits 132748107 ...
0
votes
4answers
22 views

Number theory problem based on remainder

What is the remainder when $(128)^{(128)^{128}}$ is divided by 7. My attempt: Remainder is $(128 \mod 7)^{(128 \mod 7)^{128\mod 7}}=(2)^{(2)^{2}}=16 \mod 7=2$.Is my answer and method of solving ...
1
vote
1answer
48 views

Olympiad Problem on Modular Arithmetic

Suppose $a,b,c,d$ are integers such that $$(3a+5b)(7b+11c)(13c+17d)(19d+23a)=2001^{2001},$$ prove that $a$ is even. We have $2001=3\cdot 23\cdot 29$, hence we have $3a+5b=3^{e_1}23^{e_2}29^{e_3}$ ...
3
votes
5answers
83 views

Proving $x=2,y=4$ is the only solution to $x^y=y^x$

Prove $x=2,y=4$ is the only solution to $x^y=y^x$ with the additional proviso that $x\ne y$ and $x,y$ are positive integers (if $(x,y)$ is a solution, so is $(-x,-y)$). Ideally I am looking for a ...
2
votes
0answers
26 views

Finding a lower bound

Given four positive integers $n,$ $m,$ $l$ and $k \geq 2.$ I want to find a lower bound for this expression $$|\sqrt[k]{n}+\sqrt[k]{m}-\sqrt[k]{l}|$$ in terms of these integers. Many thanks
3
votes
1answer
15 views

Non-additive asymptotic upper density: $\mathsf{d}^\star(A\cup B) \neq \mathsf{d}^\star(A)+\mathsf{d}^\star(B)$

Let $\mathsf{d}^\star$ be the asymptotic upper density on $\mathbf{N}$, that is, for each $X\subseteq \mathbf{N}$ we have $\mathsf{d}^\star(X)=\limsup_n |X\cap [1,n]|/n$. Then, is it possible to ...
0
votes
0answers
46 views

Sets with $n$ prime numbers

Let $n>2$ a natural number. We define the following sets: $$S=\{1 \leq a \leq n : (a,n)=1, a^{n-1} \not\equiv 1\pmod n\} \\ T=\{1 \leq b \leq n : (b,n)=1, b^{n-1} \equiv 1 \pmod n\}$$ ...
-3
votes
0answers
47 views

natural numbers [on hold]

The natural numbers n less than 2015 that are relatively prime to 2015 form a group G if the product nm is defined as the remainder from the division of the ordinary product nm by 2015. Find all ...
2
votes
3answers
55 views

Last digit of $1238237^{18238456}$

So, I need to find the last digit of $1238237^{18238456}$. I will work this out in $\mathbb{Z}/10\mathbb{Z}$. $$1238237^{18238456} \equiv 7^{18238456} = 49^{9119228} = 2401^{4559614} \equiv ...
4
votes
0answers
37 views

Show that $t^n-1 \mid t^m-1 \Leftrightarrow n\mid m$ [duplicate]

I want to prove the following lemma: $t^n-1$ divides $t^m-1$ in $F[t, t^{-1}]$ if and only if $n$ divides $m$ in $\mathbb{Z}$. I have done the following: $\Leftarrow $ : $n\mid m \Rightarrow ...
0
votes
1answer
27 views

Are there infinitely many $k$ for which $\frac{\sigma(k)}{k}$ is a rational square where $ \sigma(k) $ and $k$ both are square?

Is There some one who can show me if there are infinitely many $k$ for which $$\frac{\sigma(k)}{k}$$ is a rational square where $\sigma(k)$ and $k$ both are square ? Note :$\sigma(k)$ is sum ...
0
votes
0answers
26 views

How can we show the assertion?

Every natural number not of the form $4^n(8m+7)$ where $m$ and $n$ are natural numbers, can be represented as sum of three squares.
1
vote
0answers
56 views

Find the number of “p-safe numbers”

For a positive integer $p$, define the positive integer $n$ to be $p$-safe if $n$ differs in absolute value by more than $2$ from all multiples of $p$. For example, the set of $10$-safe numbers is ...
3
votes
4answers
45 views

Computing the intersection of two arithmetic sequences $(a\mathbb{Z} + b) \cap (c \mathbb{Z} + d)$

I am getting stuck writing a general formula for the intersection of two arithmetic sequences. $$ (a\mathbb{Z} + b) \cap (c \mathbb{Z} + d) = \begin{cases} \varnothing & \text{if ???} \\ ...
0
votes
5answers
33 views

How to define mathematically the integer part of an average?

Scenario: Suppose I have three numbers: 1, 3 and 4. The average of the three numbers are ...
1
vote
2answers
57 views

This expression is always a perfect square [on hold]

How to show that for $x,y\in \Bbb R$, the expression $xy+\left(\frac{x-y}{2} \right)^2$ is always a perfect square? For example $x=7, y=3$, $7\times 3+\left(\frac{7-3}{2} \right)^2=25=5^2$
-2
votes
2answers
48 views

How to find $x$ value such that $x^5\equiv 99 \pmod{21}$ using congruences [on hold]

I know congruences somewhat, however this problem is troubling me a lot. Please help me. If $17^5\equiv 5 \pmod {21}$, then at what value of x, $x^5\equiv 99 \pmod{21}$? High regards, ZION
0
votes
4answers
109 views

How many $0$s does the number $30!$ have? [duplicate]

I want to find out the number of $0$s in the number $30!$, what should I do? Is there any trick that would work for a general question of this type, like number of $0$s in $50!$ ?
2
votes
2answers
49 views

Fibonacci Cyclic Pattern [duplicate]

I want to show the Fibonacci numbers are cyclic in mod n. I have tried some small values for n and I can see this is the same. In terms of a proof, I'm thinking of using the pigeonhole principle of ...
0
votes
1answer
13 views

Perfect-power Gaussian integer factorization

In $\mathbb Z[i]$, consider a relation $\alpha\beta=\epsilon\gamma^n$ for $\epsilon$ a unit and $(\alpha,\beta)=1$. Then why are each of $\alpha,\beta$ associated to nth powers $\xi^n,\eta^n$? ...
1
vote
1answer
26 views

Definition of positive density

I have a really quick question, which I could not find an answer to with some search on the internet... What is the definition of a subset $S$ of natural numbers having a positive density? Thank you!
4
votes
2answers
90 views

Simple Number Theory question! What is the remainder when 4^999 is divided by 100?

I know I'm supposed to use modular arithmetic, but I must be messing up my process somehow. Can someone explain how to do this? $4^{999}$'s last two digits in other words (What is $4^{999}$'s ...
0
votes
1answer
31 views

My problem in the definition of Dirichlet generating function?

In the definition of Dirichlet generating function "for the square-free numbers " is: $$ \frac{\zeta(s)}{\zeta(2s)}=\sum_{n=1}^{\infty} \frac {|\mu(n)|}{n^s} $$ where $\mu$ is Moebius ...
2
votes
0answers
29 views

Let $f(x)$ be defined over all rationals $x$ in $[0,1]$ and let $F(n) = \sum_{i=1}^n f(\frac in)$

also define $$F^*(n) = \sum_{i=1\,\,(i,n)=1}^n f(\frac in)$$ then prove that $$F^* = \mu * F$$ where $\mu$ is the Möebius function and the $*$ means the Dirichlet convolution. I tried the Bell series ...
0
votes
2answers
58 views

How to denote an even number in mathematics? [on hold]

I need a sign for an even number (not $a\cdot 2$) in my formula. I tried to google it, but I saw only $2a$. Please tell me if there is a special sign?
1
vote
0answers
33 views

If $p\mid 2^n\pm1$ with $p$ and $n$ relatively prime, then $p$ is a Wieferich prime iff $p^2$ also divides $2^n\pm 1$

The Wolfram Mathworld article on Wieferich primes states: $2^{p-1}-1\equiv 0 \mod p.$ If the first case of Fermat's last theorem is false for exponent $p$, then $p$ must be a Wieferich prime ...
0
votes
0answers
39 views

Can you verify the combinatoric recurrence?

There are $2^{10} = 1024$ possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical. ...
1
vote
5answers
109 views

How to prove $\frac{2^a+3}{2^a-9}$ is not a natural number

How can I prove that $$\frac{2^a+3}{2^a-9}$$ for $a \in \mathbb N$ is never a natural number?
-6
votes
0answers
49 views

How is named this property of zero parity? [on hold]

How is named then this property of zero parity? Numbers parity Any number, except zero, multiplied twice, is an even number. A pair has two elements. Demonstration: One multiplied ...
6
votes
1answer
49 views

Can the numbers $2^m 3^n$ have an infinitely long arithmetic sequence?

I am asking for proof the set $ \{ 1,2,4,8,\dots \} \times \{1,3,9,27,\dots \} = \{1,2,3,4,6,8,9,12,\dots \}$ does not have infinitely long arithmetic sequences inside. This is OEIS A036561. What if ...
0
votes
1answer
31 views

Modular Multiplicative Inverse / Euclidean Algorithm

There's a method of obfuscating programs which is around that turns code like: my_int32 = my_value into ...
4
votes
1answer
37 views

Maximal $n$ such the the additive partition with a given product is unique.

Given $n$, there are many tuples with $a + b + c = n,0 < a < b < c$. For large $n$, different tuples may give the same products. E.g. $2+8+9=19=3+4+12,2\times8\times9=144=3\times4\times12$. ...
1
vote
1answer
21 views

Generalization of a Result on Modular Inverses

Yesterday, I attempted to solve the general system of linear congruences (I'm not sure why I've never tried this before.) \begin{align*} x &\equiv a \pmod{A} \\ x &\equiv b ...
2
votes
0answers
50 views

Find positive integer $x$, $y$, $z$ such that $2x^{2x}-1=y^{z+1}$

Find all positive integer $x$, $y$, $z$ such that $2x^{2x}-1=y^{z+1}$ I have tried to use LTE lemma but it didn't work. I think my problem is $z+1$. I can not control it. When I use LTE lemma, the ...
0
votes
1answer
32 views

Prove that $\sum_{t \vert n} d^3(t) = (\sum_{t \vert n}d(t))^2$ for all $n \in \mathbb{N}$ [duplicate]

here $d(n)$ counts the number of positive divisors of $n$. I've tried 2 things: Using Bell series. But then again it just showed me that the bell series of the square of a function is not the ...
0
votes
5answers
138 views

Why is reminder of $8^{30} / 7$ same as that of $1^{30} / 7$

I am not able to figure out why the reminder of $8^{30} / 7$ is same as that of $1^{30} / 7$. I know Euclid division $a=bq+r$ but I don't know modular arithmetic, so please explain without referring ...
-1
votes
0answers
67 views

A proposed method for further abstracting prime numbers [on hold]

I previously posted this but I framed it as a question and only inserted my results as an edit several days after the original post was created. Ulam's Spiral is a wonderful discovery. Obviously it ...
6
votes
2answers
186 views

Finding all real numbers x such that $x \lceil x \lceil x \lceil x \rceil \rceil \rceil = 88$

Question: Find all real numbers x such that $x \lceil x \lceil x \lceil x \rceil \rceil \rceil = 88$. The notation $\lceil x \rceil$ means: The least integer which is not less than $x$. My ...
4
votes
2answers
65 views

Find the maximum value of the fraction

Let $a$ and $b$ be positive integers satisfying $\frac{ab+1}{a+b}<\frac{3}{2}$. The maximum possible value of $\frac{a^3b^3+1}{a^3+b^3}$ is $\frac{p}{q}$, where $p$ and $q$ are relatively prime ...
1
vote
2answers
28 views

Modular Quadratic Equation

I'm trying to solve that equation: $x^2-3x-5\equiv0\pmod{343}$ I've completed the square as follows: $x^2-3x-5 \equiv x^2+340x-5\equiv(x+170)^2-170^2-5\pmod{343}\\ (x+170)^2 \equiv 93\pmod{343}\\ ...
2
votes
3answers
44 views

Elementary number theory, compute this sum

My first problem is the following: prove that $4|\sigma(4n+3)$ for any positive integer $n$. This is what I tried: if $1\le m\le n$, then $\sigma(n)=\sum_{\gcd(n,m)=m}m;$ Now the sum of all integers ...
1
vote
2answers
47 views

Solving two diophantine equations.

Find at least one 5-tuple of positive integers which satisfy the following two equations $$a^2-d^2=3(b^2-c^2)$$ $$e^2-b^2=3(d^2-c^2)$$ such that no three of the 5 positive integers $a, b, c, d, e$ ...
2
votes
2answers
79 views

Find a recursion (combinatorial)

Consider sequences that consist entirely of $ A$'s and $ B$'s and that have the property that every run of consecutive $ A$'s has even length, and every run of consecutive $ B$'s has odd length. ...
0
votes
3answers
39 views

Difficult nonlinear system based on max value

Let $ (a,b,c)$ be the real solution of the system of equations $ x^3 - xyz = 2$, $ y^3 - xyz = 6$, $ z^3 - xyz = 20$. The greatest possible value of $ a^3 + b^3 + c^3$ can be written in the form $ ...
1
vote
4answers
58 views

remainder of $a^2+3a+4$ divided by 7

If the remainder of $a$ is divided by $7$ is $6$, find the remainder when $a^2+3a+4$ is divided by 7 (A)$2$ (B)$3$ (C)$4$ (D)$5$ (E)$6$ if $a = 6$, then $6^2 + 3(6) + 4 = 58$, and $a^2+3a+4 ...
0
votes
2answers
42 views

Use proof by contradiction to prove that if $a$ and $b$ are odd integers, then $4 \nmid (a^2+b^2)$.

I have been working through the following proof: Use proof by contradiction to prove that if $a$ and $b$ are odd integers, then $4 \nmid (a^2+b^2)$. Below, I have included screenshots of the ...
0
votes
3answers
48 views

Chinese remainder theorem for three equations?

Is there a straightforward approach for solving the Chinese Remainder Theorem with three congruences? $$x \equiv a \bmod A$$ $$x \equiv b \bmod B$$ $$x \equiv c \bmod C$$ Assuming all values are ...
2
votes
1answer
55 views

How to show $n$ is a prime number?

Let $a$ and $n$ be integers greater than 1. Suppose that $a^n-1$ is a prime. Show that $a=2$ and $n$ is a prime. What can you say about primes of the form $2^n+1$? By ...
0
votes
0answers
52 views

Curious GCD Divisibility Relation

In some of my recent work, I have accidentally discovered in an extremely convoluted manner the following result: Suppose $a,b$ are positive integers less than some other positive integer $c$, and ...
0
votes
0answers
15 views

$S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$, $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ iwth composite and prime numbers

I have two sets with $n>2$ natural number: $S=\{1\le a \le n:(a,n)=1,a^{n-1}\not\equiv 1\pmod n\}$ $T=\{1\le b \le n:(b,n)=1,b^{n-1}\equiv 1\pmod n\}$ Can anyone explain me if there are prime ...