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

learn more… | top users | synonyms (1)

21
votes
4answers
1k views

Visualizing the factorial

Often in basic mathematics, we can visualize things very easily, which I believe helps understanding (instead of just working out a number theoretical proof). For example: $$(n+1)^2 - n^2 = (n+1) +n$$ ...
3
votes
1answer
35 views

How many pairs of $(x, y)$ satisfied this equation

I need help to solve in $\mathbb{Z}$ the following equation $$yx^{2}+xy^{2}=30$$ I tried to solve it by factor $30$ to $5\times 6$ and I get those two pairs $(2, 3) \& (3, 2) $... is their any ...
2
votes
2answers
392 views

Stars and Bars vs PIE

I randomly made up this question so I could check: There are $3$ kids and $6$ gifts, how many ways to distribute so that each kid has at least one gift. Obviously, $**|**|**$ there are ...
0
votes
0answers
34 views

Find number of element in $\{m\in\mathbb N:m\leq n\text{ and }m\text{ has the digit 3}\}$.

Inspired by a youtube video claiming that "almost all positive integer has the digit 3", I set myself a challenge: Give a formula, in terms of $n$, for the number of positive integer that is less ...
-2
votes
3answers
99 views

Division problems

I came across these problems : 1) Find the lowest natural number $k$ that satisfies the condition : $ 7 \mid A$ , where $A = 194^{19} + 125^{14} + k $ 2) Find the different prime numbers ...
5
votes
3answers
445 views

Problem Solving Positive Integers

This is a very interesting word problem that I came across in an old textbook of mine. So I know the maximum value of the HCF has to be a factor of $540$ and mayhaps the Euclidean Algorithm, but other ...
4
votes
1answer
60 views

How to prove that any natural number $n \geq 34$ can be written as the sum of distinct triangular numbers?

Sloane's A053614 implies that $2, 5, 8, 12, 23$, and $33$ are the only natural numbers $n \geq 1$ which cannot be written as the sum of distinct triangular numbers (i.e., numbers of the form ...
5
votes
2answers
191 views

Prove that every integer $n\geq 7$ can be expressed as a sum of distinct primes.

My teacher said to use Bertrand's postulate and I have tried this for so long and I seem to go nowhere. Help would be appreciated. EDIT: Here's what I've done in my proof so far (I need help ...
3
votes
2answers
118 views

at least one of 100 consecutive integers is relatively prime to all natural numbers less or equal 100

For an arbitrary integer $n$ define $A_n=\{i|n \leq i \leq n+99 \text{ where }i\text{ is an integer}\}$ (i.e. $A_n$ is 100 consecutive integers) Is it true that for any integer $n$ there is an ...
2
votes
3answers
72 views

Why would the cubic have $5$ roots?

The polynomial $P(x)$ is cubic. What is the largest value of $k$ for which the polynomials $Q_{1}(x) = x^{2}+(k-29)x-k$ and $Q_{2}(x) = 2x^{2}+(2k-43)x+k$ are both factors of $P(x)$? $P(x) = ...
3
votes
2answers
47 views

Find the least $N$ so there is no square

Find the least positive integer $N$ such that the set of $1000$ consecutive integers beginning with $1000 \cdot N$ contains no square of an integer. Let $x^2$ appear before $1000N$ so: $(x+1)^2 ...
-1
votes
0answers
66 views

How does constructing numbers in a set theoretic way help mathematics?

I recently read that the natural numbers can be constructed within the framework of the Zermelo-Fraenkel axioms via de axiom of infinity, where, with $n$ a natural number $n+1=n\bigcup \{n\}$ and ...
0
votes
2answers
59 views

How many divisors of the combination of numbers?

Find the number of positive integers that are divisors of at least one of $A=10^{10}, B=15^7, C=18^{11}$ Instead of the PIE formula, I would like to use intuition. $10^{10}$ has $121$ divisors, ...
1
vote
1answer
42 views

How to use Principle of Inclusion-Exclusion here?

A while ago I posted a question: Coloring a Grid. Online, I seem to have stumbled upon a usage of PIE AOPS Wiki Solution AIME II #9. (1) Now, I have experience with PIE, but I do not see how to ...
12
votes
2answers
469 views

Show divisibility by 7

I was stuck at this question: Suppose $a^2+b^2=c^2$ for $a,b,c \in \mathbb Z$, and neither $a$ nor $b$ is a multiple of 7. Show that $a^2-b^2$ is a multiple of 7 I tried to write $b^2$ as ...
1
vote
1answer
61 views

Probability of getting a five digit number divisible by 5 but with no two consecutive digits identical

A five digit number is written down at random. What is the probability of getting a number that is both divisible by 5 and doesn't have any 2 consecutive digits identical? I tried to analyse the ...
1
vote
2answers
185 views

How come $\ n\ $ always divides at least one of the item of the sequence?

Given positive integer$\ \displaystyle n,\ $ the sequence is: $\displaystyle 2^n$ $\displaystyle 2^n - 2^{n-1}$ $\displaystyle 2^n - 2^{n-1} + 2^{n-2}$ $\displaystyle 2^n - 2^{n-1} + 2^{n-2} - ...
1
vote
2answers
49 views

To calculate the remainder of (111…) + (222…) + (333…) + (444…) + (555…) + (666…) +(777…) by 37

To Evaluate the remainder Question: $ (111...) + (222...) + (333...) + (444...) + (555...) + (666...) +(777...)$ mod $37$ In each bracket, the single digit $(1, 2, 3, ..., 7)$ is written $110$ ...
-1
votes
2answers
101 views

Solve $x,y\in \mathbb{Z}$ [closed]

Solve for $x,y\in \mathbb{Z}$ $$x^{6}=y^{2}+53$$ I tried but I couldn't complete
0
votes
2answers
41 views

Can we obtain the pair $(1,50)$ with these following operations?

It's a problem from some russian competition: We're given a card with two positive integers $(a,b)$ and we have tree machines which generate another card from the one we insert on it(I assume we ...
1
vote
0answers
22 views

Proof of x = 0 modulo 3 only if the sum of its digits 0 modulo 3 [duplicate]

Okey, lets beggin from a helpfull proposition I've already proved: $$$$ if $a_i\equiv b_i\:\forall 0\le i\le m$ then to any $m$ numbers: $p_1,p_2,...,p_m\in \mathbb{Z}$ $$\sum ...
1
vote
2answers
70 views

Ways of coloring the $7\times1$ grid (with three colors)

Hints only please! A $7 \times 1$ board is completely covered by $m \times 1$ tiles without overlap; each tile may cover any number of consecutive squares, and each tile lies completely on the ...
2
votes
2answers
37 views

Binary expansion, finding the greatest power of $2$ less than a given number

I'm looking to better understand binary for a CS50 problem set. I'm not understanding transferring decimal notation to binary. For example, use 237. How to find the largest power of $2$ less than ...
2
votes
2answers
58 views

What is the remainder when 50^51^52 divided by 11?

To find the remainder: $$50^{51^{52}} \mod 11$$ I have solved till: $$6^{51^{52}} \mod 11$$ But not able to proceed further. Help please.
4
votes
4answers
105 views

Greatest of the numbers given [duplicate]

To find out the greatest among the number given below: $3^{1/3}, 2^{1/2}, 6^{1/6}, 1, 7^{1/7}$ I have plotted the following graph using graph plotter which is shown below: It can be concluded that ...
7
votes
0answers
123 views

Dividing the whole into a minimal amount of parts to equally distribute it between different groups.

Suppose we have a finite amount of numbers $x_1, x_2, ..., x_n$ ($x_i\in\mathbb{N}$) and an object that should be divided into parts in such a way that it can be without further dividing distributed ...
2
votes
1answer
56 views

Least $j$ such that $j^2 - k$ is a square?

Given a positive integer $k$, how do we find the least integer $j$ such that $j^2-k$ is a perfect square? E.g. say $k = 75 = 25 \times 3 = 15 \times 5$. How do we know that the least $j$ in this case ...
5
votes
0answers
105 views

Are there papers or books that explain why Bernhard Riemann believed that his hypothesis is true?

I would like to know what are the mathematical reasons for which Bernhard Riemann believed that his hypothesis is true, and I would like to know if those mathematical reasons were cited in his ...
1
vote
0answers
32 views

Does Bezout's Identity hold for Zero cases?

In some places I see Bezout's Identity stated for any two non-zero numbers $a$ and $b$. In other places it is stated that $a$ and $b$ are not both zero (so one of them can be). But doesn't Bezout's ...
2
votes
2answers
53 views

Terms of a certain recurrence

Let $a_1, a_2\dots $ be a sequence of reals such that $a_1 = a_2 = 1$, and $$a_{n + 2} = \frac{a_{n + 1}^3 + 1}{a_n}$$ for $n \ge 1$. It appears to be the case that all of these values are integers. ...
2
votes
1answer
26 views

For any $N$ and $B$, is there always a $B$-smooth relation $x + y \equiv 0 \pmod{N}$?

Let $N$ be any integer and $B \geq 2$ be a smoothness bound. Does there always exist $B$-smooth integers $x,y$ such that: $$x + y \equiv 0 \pmod{N}\text{ ?}$$ My only progress is that I know the ...
2
votes
0answers
31 views

Generating all coprime pairs

The Wikipedia article on coprime integers has a brief section on generating all coprime pairs. All pairs of positive coprime numbers $(m,n)$ (with $m>n$) can be arranged in two disjoint ...
1
vote
3answers
73 views

find the complex number $z^4$

Let $z = a + bi$ be the complex number with $|z| = 5$ and $b > 0$ such that the distance between $(1 + 2i)z^3$ and $z^5$ is maximized, and let $z^4 = c + di$. Find $c+d$. I got that the ...
0
votes
1answer
65 views

Show that $(t^m-1)/(t^n-1)$ is a square if and only if $(\exists s \in \mathbb{Z})\ m=np^s$

I want to show the following lemma: Assume that the characteristic of the field $F$ is $p$ and $p>2$. Then $(t^m-1)/(t^n-1)$ is a square in $F[t, t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in ...
-2
votes
2answers
57 views

Stuck on large numbers [closed]

i've got a problem. I need to prove that $43^{47}-17^{17}$ is divisible by $10$. I think that somehow I have to prove that the number ends with a $0$. Any ideas?
1
vote
1answer
32 views

Fermat primality test and Fermat pseudoprime

What is the difference between Fermat primality test and Fermat pseudoprime?Can anyone explain me how we use them ?
0
votes
1answer
33 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
24 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
60 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}$ ...
5
votes
8answers
181 views

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

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
28 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
25 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 ...
3
votes
3answers
70 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 ...
8
votes
4answers
149 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 ...
2
votes
2answers
37 views

Remainder Dividing Repunits

If $n = 11111 \ldots 1$ (1 repeated 123 times.) Then find the remainder when $n$ is divided by 271? I know I can write this in the form of a sum of a gp but it doesn't help to find the remainder... ...
0
votes
1answer
28 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
35 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
67 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 ...
4
votes
4answers
53 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 ???} \\ ...
-1
votes
5answers
46 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 ...