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

learn more… | top users | synonyms (1)

-1
votes
1answer
31 views

Is this true for every prime $p>2$ , if$ m$ is even integer number then $m$ can't be written as :$m=\prod _{i=1}^{r}{p_i}^{a_i}$?

I would like to show if $p_i$ an odd prime for all $i=1,\cdots,r$ and suppose that there is an integer $m$ such that 2 divides $m$ , I would like to show if $m$ can be written as follow: ...
0
votes
0answers
28 views

What is the difference between these two numbers?

A number 10,10,101 when multiplied with N gives product P, such that N is any no with only 1 as its digit (eg. N = 11,111,1111,.......) . We have to find how many different digits can be possible in ...
1
vote
1answer
33 views

Basic questions about field homomorphism extension

I learned that one can extend the homomorphism "injection" $k\hookrightarrow \Omega$ (algebraic closure) to a morphism $u:k[a]\to \Omega$ where $a\in \Omega$ is algebraic over $k$ such that the ...
5
votes
1answer
74 views

Does there exist a prime number $p$ such that $p^2 \mid 2^{p-1}-1$?

Does there exist a prime number $p$ such that $p^2 \mid 2^{p-1}-1$ ? I tried for some small number $p$ and I think that it does, but I don't know how to prove this.
3
votes
1answer
32 views

Period of a Recurrence Relation

Let {$x_n$} be such a recurrence relations that obeys the following: For fixed naturals $a,b$, $x_ {n+1}$ is the least prime divisor of $ax_n+b$. Calculations showed that{$x_n$} appears to be ...
1
vote
2answers
34 views

Proving sum of product forms a pattern in n * nnnnnn…

I am consider a problem regarding numbers which are, in decimal, one digit repeated - for instance, $88888888$ is such a number. In particular, I am looking at the following problem: The sum of ...
1
vote
2answers
29 views

Divisibility (algebra, number theory).

Suppose you have $$a b c = m$$ $$a|y$$ $$b|y$$ $$c|y$$ Does that imply that $$m|y$$ $$am_1 = y$$ $$bm_2 = y$$ $$cm_3 = y$$ $$mm_1 m_2 m_3 = y^3$$ ??
0
votes
1answer
35 views

What is the largest prime number in the denominator of a fraction that creates a decimal that repeats every 4 digits?

I was studying a Target question for Math League competitions, and after a few hours of pondering, I finally came up with the following method of solving the mentioned problem: For any decimal, it is ...
5
votes
4answers
78 views

If the $81$ digit number $111\cdots 1$ is divided by $729$, the remainder is?

If the $81$ digit number $111\cdots 1$ is divided by $729$, the remainder is? $729=9^3$ For any number to be divisible by $9$, the sum of the digits have to be divisible by $9$. The given number ...
0
votes
2answers
72 views

Evaluate all the square roots of 4 mod 77. [closed]

I have an exam coming up an this will be one style of question can anyone please walk me through how it is done? Sorry I am just totally confused and do not how to start Evaluate all the square roots ...
0
votes
2answers
80 views

If $G = \{a + b: a, b \in A\}$ a group, then is $A$ a group?

Let $A $ be a subset of an abelian group $H$. Then if $G = \{ a + b : a, b \in A\}$ is a group and $A$ is closed under taking negatives, then is $A$ also a group?
0
votes
1answer
21 views

Why I can't have duplications for quadratic residues when I have some $p$ prime greater than 2 ?(and also the max numb. of quad.res)

I've started studying number theory and I am not understanding the following result: Let $p$ be a prime other than $2$. If there are two numbers $u$ and $v$ such that $u^2\equiv v^2 \mod p$ ...
4
votes
4answers
55 views

If $a\mid b^2, b^2\mid a^3,\ldots ,a^n\mid b^{n+1},b^{n+1}\mid a^{n+2},\ldots$ then $a=b$ [duplicate]

I'm stuck with this problem : Let $a,b$ positive integers such that $$a\mid b^2, b^2\mid a^3,\ldots ,a^n\mid b^{n+1},b^{n+1}\mid a^{n+2},\ldots$$ Show that $a=b$. If were $ b > a $ then $\lim_{n ...
3
votes
4answers
103 views

Congruences and prime numbers

I was first asked to show that a product of numbers of the form $4k+1$ also has this form. I got stuck on the next part: Deduce that if $n \equiv −1 \pmod 4$ and $n > 0$ then $n$ must have a prime ...
2
votes
2answers
49 views

Co-Prime numbers

If two integers $a$ and $b$ are co-prime, how can I show that $a$ and $b^n$ are co-prime? I am guessing that first i must show a base case and then use induction but I am not sure how to proceed. ...
1
vote
2answers
39 views

HOTT proof of transitivity of ordering of natural numbers

So slowly going through HOTT book I finished chapter 1,where near the end it is defined $n \leq m \equiv \sum_{k: \mathbb{N}} a+k =_\mathbb{N} b$ Now I want to prove that if I have $a,b,c:\mathbb{N}$ ...
2
votes
0answers
40 views

Existence of an isomorphism $\Bbb{Z}_{n}^{\times} \rightarrow \Bbb{Z}_{\phi(n)}^{+}$

I am considering the multiplicative group of units modulo $n$ which I shall refer to as $\Bbb{Z}_{n}^{\times}$. I read somewhere that $$\Bbb{Z}_{n}^{\times} \cong \Bbb{Z}_{\phi(n)}^{+}$$ where ...
0
votes
1answer
20 views

for which conditions of postive integer $n, m >0$ :$\dfrac{\sigma{(n)}}{n}\leq\dfrac{\sigma{(n+m)}}{n+m}$ hold?

I would like to know more about behavior of growth rate of sum divisor function I accross this problem then :for which conditions for $n, m$ : $$\dfrac{\sigma{(n)}}{n}\leq\dfrac{\sigma{(n+m)}}{n+m}$$ ...
1
vote
1answer
16 views

Asymptotic elements of a sequence of of gaps given the average asymptotic function.

If the average consecutive difference of a sequence of numbers is asymptotically the same as $f(n)$. Then what can be said about numbers in the sequence, asymptotically as $n \to \infty$. Let ...
1
vote
2answers
39 views

Without using prime factorization, show if $m\mid n^2$ then $\gcd(m,n^2/m)\mid n$

It's easy to use prime factorization to show: If $m\mid n^2$ then $\gcd(m,n^2/m)\mid n$. Can anybody find some other proof - perhaps a simple reduction of some sort? Maybe solving $m^2x + ...
1
vote
0answers
31 views

Solving a Diophantine Equation with 2 variables

This is my answer for the following question: Find all natural numbers $(a,b)$ for which $a^b-b^a=1$. When $a$ or $b$ equals $1$, $(a,b)=(2,1)$ is trivial. If $a,b>1$, I generalized the problem ...
1
vote
0answers
37 views

$\exists\ n \gt 34131$ with more than $7$ odd divisors $d_i \gt 1$ such as when $d_i+1$ are accumulated in increasing order to $1$ the sums are prime?

In the same style as a previous test, I did a little test today looking for all the numbers such as the odd divisors, ordered in increasing order excluding $1$, when they are accumulated one by one to ...
3
votes
3answers
75 views

An identity involving $[\sigma(n)]^2$

For a positive integer $n$, let $\sigma(n)$ denote the sum of the divisors of $n$. For example, $\sigma(1)=1$, $\sigma(2)=3$, $\sigma(4)=7$, etc. I would like to prove the following identity: For ...
2
votes
0answers
133 views

Prove that $(a-b)^n\mid (a^n-b^n) \iff n=1$ under given conditions

Suppose that $a,b,(a-b)$ are pairwise co-prime (i.e. $a\perp b\perp (a-b)\perp a$), and that $\frac{a}{2}<b<a$, where $a$ and $b$ are both positive integers greater than $2$. Let $n$ be odd. ...
2
votes
3answers
56 views

Problem on factorials and divisiblity of number theory [closed]

How do I prove that $a!b!$ completely divides $(a+b)!$
-1
votes
1answer
23 views

Prove that the number of zero divisors in $\mathbb Z / n\mathbb Z$ for specific element $k$ is $n / \mbox{ggT}(n,k)$

Let $k$ and $n$ be two given natural numbers, then \begin{align*} \left| \left\{ i \in \{0,\ldots,n-1\} : n \mbox{ divides } i \cdot k \} \right\} \right| & = \frac{n}{\operatorname{ggT}(n,k)} ...
0
votes
1answer
18 views

Show $a^2+b^2 \equiv 0 \mod p$ has no solutions except $a \equiv b \equiv 0 \mod p \Longleftrightarrow -1$ is a non-square modulo $p$.

I was looking at this question: Field in $\mathbb{F}_3$. One of the answers states: "So you have to show that $a^2+b^2=0$ has no solutions modulo $7$ besides $a=0=b$ (modulo $7$, of course). Can you ...
1
vote
1answer
50 views

Possible circular reasoning in textbook proof that $\lceil x+m\rceil=\lceil x\rceil +m$

The goal is to prove that $\lceil x+m\rceil=\lceil x\rceil +m$, where $x$ is a real number and $m$ is an integer. The book outlines the following proof: Write $x=n-\epsilon$, where $n$ is an ...
8
votes
3answers
105 views

Last $500$ digits of $2015!-1$

As the title says, I'm looking for the last $500$ digits of $2015!-1$. I assume it's a repetition of zeroes from the factorial, so the final result is a lot of $9$-s, but I can't formulate a solution ...
5
votes
1answer
94 views

Let $H_n=1+1/2+..+1/n=p_n/q_n$. Find all $n$ such that $3|p_n$

Problem: Let $H_n=1+1/2+..+1/n=p_n/q_n$ with $\gcd(p_n,q_n)=1$. Find all $n$ such that $3|p_n$. Observations: Note that $H_n=(n!/1+n!/2+...+n!/n)/n!$. If $3|p_n$, the numerator of this fraction ...
1
vote
1answer
38 views

Determine what when multiplied with $180$ gives a perfect cube

Recently, at a math competition, I was given the following question: Determine the smallest number that gives a perfect cube when multiplied by $180$ . I had thirty seconds to solve this question and ...
1
vote
4answers
78 views

Prove by induction that $8^{n} − 1$ is divisible by $7$

Prove by induction that $8^{n} − 1$ for any positive integer $n$ is divisible by $7$. Hint: It is easy to represent divisibility by $7$ in the following way: $8^{n} − 1 = 7 \cdot k$ where k is a ...
1
vote
0answers
44 views

If $a^n+n^b\mid c^n+n^d$ for every $n$ then $c=a^k$ and $d=kb$ .

I made a generalization of the following problem (it's a problem from the IMO shortlist in some year) : Let $a,b$ be fixed positive integers . If : $$a^n+n \mid b^n+n$$ for every positive integer ...
1
vote
4answers
65 views

Prove if $2|x^{2} - 1$ then $8|x^{2} - 1$

I have seen this question posted before but my question is in the way I proved it. My books tells us to recall we have proven if $2|x^{2} - 1$ then $4|x^{2} - 1$ Using this and the fact $x^{2} - 1 ...
2
votes
2answers
62 views

Find all positive integers $n$ such that $n+2008$ divides $n^2 + 2008$ and $n+2009$ divides $n^2 + 2009$

I wrote $$ \begin{align} n^2 + 2008 &= (n+2008)^2 - 2 \cdot 2008n - 2008^2 + 2008 \\ &= (n+2008)^2 - 2 \cdot 2008(n+2008) + 2008^2 + 2008 \\ &= (n+2008)^2 - 2 \cdot 2008(n+2008) + 2008 ...
0
votes
1answer
20 views

Can the remainder $r_2$ in the following be larger than $\frac{r_0}{2}$?

Let $n$ and $r_0 < n$ be integers. We define: $r_1 = n$ mod $r_0$ $r_2 = n$ mod $r_1$ Where we restrict $0 < r_1 < r_0$ and $0 < r_2 < r_1$. Is it possible for $r_2$ to be larger ...
0
votes
0answers
32 views

A question in number theory…doubt clarification…!!!

I am very new to Number Theory. Got the following thing in notes which I am unable to do: $P$ is a set with elements $P=\{u_0,u_1,\ldots,u_{n-1}\}$. It was given that for different values of $n\geq ...
1
vote
2answers
54 views

Prove that $τ(m^n)$ and $n$ are coprime $(m,n ∈ N^+)$

We have that $τ(n)=\sum_{d|n} 1$ is the number of dividers of n. Dividers of $m^n$ are $1,m,m^2,...,m^n$ then we have that $τ(m^n)=n+1$. Is this correct so far? Now we must prove that $τ(m^n)$ and ...
1
vote
2answers
42 views

Elementary theory of numbers and congruences

How to find solutions for: $x^2\equiv 8\pmod{ 3}$ $x^2\equiv 15\pmod{ 31}$ $x^2\equiv 54\pmod{ 7}$ $x^2\equiv625\pmod{9973}$
6
votes
3answers
223 views

Fill a cube with small cubes with different integer side lengths

We are given two (potentially unlimited) sets of cubes, say red cubes (with side $n$) and white cubes (with side $m$), with $m,n \in \mathbb{N} \setminus \{0\}, m \neq n$ (let's assume $n>m$). ...
6
votes
3answers
47 views

Modular arithmetic problem (mod $22$)

$$\large29^{2013^{2014}} - 3^{2013^{2014}}\pmod{22}$$ I am practicing for my exam and I can solve almost all problem, but this type of problem is very hard to me. In this case, I have to compute this ...
0
votes
1answer
40 views

If $a$ and $b$ are coprime then $7a+3b$ and $2a-b$ are also coprime [closed]

I am trying to prove following: If $a$ and $b$ are coprime, then $7a+3b$ and $2a-b$ are also coprime. Thanks.
-2
votes
1answer
53 views

Solve the $5^{45} \pmod{2017}$ [closed]

How to find solutions of $5^{45} \pmod{2017}?$ Thanks
3
votes
3answers
108 views

Solve the congruence $3x^2+x+8\equiv 0 \pmod{11}$

How to find the solutions of this congruence? $$3x^2+x+8\equiv 0 \pmod{11}$$ I need to find the inverse of $3$, and there I have a problem.
2
votes
1answer
134 views

Prove: A 9 element subset of ${1,2,…,99}$ must have two distinct subsets with the same sum.

APMO 2014 Problem 4: Prove: A 9 element subset of ${1,2,...,99}$ must have two distinct subsets with the same sum. I am having a lot of trouble with this problem. The official solution: ...
0
votes
2answers
83 views

find a number p such that the number $(2)(3)(5)(7)…(p) + 1$ is not prime

find a prime number p such that the number $(2)(3)(5)(7)...(p) + 1$ is not prime. attempt: let n be the non prime number. therefore: $$(2)(3)(5)(7)...(p) + 1 = n $$ but n is not prime so it is ...
-2
votes
1answer
102 views

Equation involving floor function: [closed]

Given n a natural number, find $x$ (positive real number) such that: $$ 6\lfloor x \rfloor=n, $$ where $ \lfloor x \rfloor $ represents the value of the floor function in x.
6
votes
4answers
109 views

Prove: $\forall$ $n\in \mathbb N, (2^n)!$ is divisible by $2^{(2^n)-1}$ and is not divisible by $2^{2^n}$

I assume induction must be used, but I'm having trouble thinking on how to use it when dealing with divisibility when there's no clear, useful way of factorizing the numbers.
0
votes
2answers
42 views

How many sets of 8 3-digit consecutive even numbers are possible such that product when divided by 5 gives perfect cube?

The sum of eight three-digit consecutive even number is S.When S is divided by 5, it results in a perfect cube.How many sets of such eight numbers are possible?
4
votes
2answers
96 views

How to find out if a number is a hundred or thousand?

The question might raise people's eyebrows but I have been googling and I don't know the keyword to search for. I just don't know the mathematical term. What I'm trying to do is I want to round a ...