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

learn more… | top users | synonyms (1)

3
votes
2answers
85 views

Let $a,k,m$ be integers. Prove that $\gcd(ka,km) = k\gcd(a,m)$.

Here is what I got so far: Let $\gcd(ka,km) = d$ Then by the Euclidean Algorithm, we have integers $s,t$ such that: $$s(ka) + t(km) = d \implies k|d $$ Let $$d/k = g = sa + tm. \tag{1}$$ So now ...
5
votes
3answers
446 views

Prime Number in triangle

I had a question here, the measures of the sides of a right triangle (a single unit) can be prime numbers? If they can not, why?! But, if you can, could you help me find an example?
1
vote
1answer
112 views

Last 3 digits of $2012^n$

Let $n\in\mathbb{N}$ such that the base $10$ expansion of $2012^n$ is $?\,?\,?\ldots ?\,4\,?\,4$ where $?$ is an unknown digit. Find all the possible values of the digit between the $4$s.
1
vote
0answers
100 views

A Gauss sum over a field.

Let $K$ be a field (not necessarily $\mathbb C$) and let $\zeta=\zeta_n$ be a primitive $n$th root of unity in $\bar K$. I would like to know if there is a formula calculating $$ \sum_{k=1}^n ...
3
votes
2answers
147 views

On proving the convergence of $1/n^2\sum_{1\le k\le n}\varphi(k)$

Let $$\Phi_n=\frac{1}{n^2}\sum_{k=1}^n\varphi(k).$$ How one can show that $\Phi_n$ is convergent sequence? (Here, $\varphi$ denotes the Euler's totient function.) And please, without any monster ...
4
votes
2answers
146 views

If $x^2+ax+b=0$ has a rational root, show that the root is an integer. [duplicate]

So far I have Assume $a,b,x,y$ are integers; $\frac xy$ is rational; and that $\frac xy$ is in simplest form. WTS: $\frac xy$ is integer So $(\frac xy)^2 + a(\frac xy) + b = 0$; ${x^2\over y^2} = ...
2
votes
1answer
118 views

if $a/b+c/d=n$ then $|b|=|d|$

I have to prove that if gcd$(a,b)=1$ and gcd$(c,d)=1$ and if $a/b+c/d=n\in\mathbb{Z}$ then $|b|=|d|$. Here is my approach: $$a/b+c/d=\frac{ad+bc}{bd}=n$$ so $bd\mid (ad+bc)$. Also gcd$(a,b)=1$ and ...
-2
votes
3answers
501 views

Find an algorithm to compute $(1! \cdot 2! \cdot3!\cdots n! ) \,\%\, x$.

You need to find the product of first n factorials $1! \cdot 2! \cdots n!$ modulo $109546051211.$ $1 \le n \le 10^7$. I need a fast algorithm for this.
1
vote
2answers
119 views

Divisibility of sequence

Let the sequence $x_n$ be defined by $x_1=1,\,x_{n+1}=x_n+x_{[(n+1)/2]},$ where $[x]$ is the integer part of a real number $x$. This is A033485. How to prove or disprove that 4 is not a divisor of any ...
4
votes
1answer
103 views

$1^k+2^k+\cdots+n^k\mod n$ where $n=p^a$.

My friend said that for any $n=p^a$, where $p$ is odd prime, $a$ is positive integer then: If $k$ is divisible by $p-1$ then $1^k+2^k+\cdots+n^k\equiv -p^{a-1}\pmod{p^a}$. I am very sure that his ...
1
vote
1answer
354 views

Hausdorff dimension of the set of rational numbers within a certain interval?

Intro: The Hausdorff dimension (also known as the Hausdorff–Besicovitch dimension) is an extended non-negative real number associated with any metric space. In general the Hausdorff dimension ...
0
votes
0answers
105 views

is $\sqrt{n!}\notin\mathbb{Z}$ for $n>1$ true? [duplicate]

Is it true that $\sqrt{n!}\notin\mathbb{Z}$ for $n>1$? This is what I did: By induction: for $n=2$ its trivial ($\sqrt{2}$ is irrational). Suppose its true for some $n\in\mathbb{N}$, then the ...
9
votes
3answers
293 views

The integer $c_n$ in $(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$

For non-negative integer $n$, write $$(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$$ where $a_n,b_n,c_n$ are integers. For any non-negative integer $m$, prove or disprove ...
1
vote
2answers
305 views

Solve the following system of simultaneous congruences:

\begin{gather} 3x\equiv1 \pmod 7 \tag 1\\ 2x\equiv10 \pmod {16} \tag 2\\ 5x\equiv1 \pmod {18} \tag 3 \end{gather} Hi everyone, just a little bit stuck on this one. I think I am close, but I must be ...
1
vote
1answer
78 views

Part of a proof for Wilson's Theorem

I am looking at this proof of Wilson's Theorem, and it uses a fact that for a prime $p$ and $a,a^{-1} \in \mathbb{Z}_p^\ast$, $$a = a^{-1} \text{ if and only if } a = 1,p-1.$$ For the $\Leftarrow$ ...
2
votes
4answers
84 views

Is there any solution to the following system of equations?

Is there any solution to the following system of diophantine equations? $$ \left\{\begin{array}{l} 2.a^2 = b^2+c^2+d^2 \\ a^2 = e^2+f^2+g^2 , & \mbox{with }((a,b,c,d,e,f,g)>2)\in N\mbox{ and ...
2
votes
1answer
770 views

Prove that no positive integer is both even and odd, and that all positive integers are either even or odd

What is says on the can: Prove that no positive integer is both even and odd, and that all positive integers are either even or odd. This, of course, depends on defining even and odd. For extra ...
4
votes
1answer
197 views

Find all natural numbers $n$ that divide $1^n + 2^n + \cdots+ (n-1)^n$

Problem: Find all natural numbers $n$ that divide $1^n + 2^n + \cdots + (n-1)^n$ Actually, this isn't homework, but I'll add a homework tag just in case. The problem is from Santos' Number theory for ...
1
vote
0answers
51 views

Question about partitions and primes.

Let $A_1\cup A_2\cup\cdots\cup A_n = P$ , where $P$ stands for the set of odd primes $<\sqrt{x}$ and $A_i$ is nonempty. Also $\#A_k\gg \# A_l$ iff $k>l$ ($\#$ is cardinality ). In fact we ...
0
votes
2answers
206 views

Prove $\log_a(b)$ is irrational given that $a, b$ are positive distinct primes.

I know this is a classical proof by contradiction exercise, and there are full solutions else where, doing a quick search I didn't find any, but I would approach this question like this: Suppose ...
0
votes
1answer
73 views

Counting elements of reduced residue systems modulo one number which are smaller than another

Euler's totient function for a prime power input can be written as follows: $$\phi(p_n^k) = (p_n - 1)p_{k-1}$$ This function counts those numbers that are smaller than $p_n^k$ but which are also ...
21
votes
1answer
566 views

Is it always possible to factorize $(a+b)^p - a^p - b^p$ this way?

I'm looking at the solution of an IMO problem and in the solution the author has written the factorization $(a+b)^7 - a^7 - b^7=7ab(a+b)(a^2+ab+b^2)^2$ to solve the problem. It seems like it's always ...
0
votes
1answer
79 views

If $p$ prime and $0<x<y<z<p$ with squares congruent mod $p$, then $x+y+z\mid x^2+y^2+z^2$

If $p$ is a prime number and $x,y,z\in N$ such that $0<x<y<z<p $ and $x^2, y^2, z^2$ give the same remainder when divided by $p$, then $ x^2+y^2+z^2$ is divisible by $x+y+z$ ? Any advice ...
6
votes
2answers
87 views

Congruence Equation $3n^3+12n^2+13n+2\equiv0,\pmod{2\times3\times5}$

How to solve the following congruence equation? $$3n^3+12n^2+13n+2\equiv0,\pmod{2\times3\times5}$$ If $t_n$ be the $n$th triangular number, then ...
5
votes
3answers
617 views

Find the remainder of $(2n)^x\, ,n \in \Bbb N \,\,$ when divided by $100$?

There is no specific question as such. I am preparing for an aptitude exam, and am stuck at this particular point when we are required to find the last two digits/remainder when divided by 100 of an ...
1
vote
1answer
90 views

Alternative proof to numbers game - Numbers as digits

$\quad$A couple days ago, I heard of a simple numbers game(or trick), and decided to prove it. I succeeded (I think), but don't really like the way I did it, so I was wondering if someone could think ...
3
votes
2answers
482 views

Taking modulo by product of 2 primes

If we are given a number $n$, and two primes $p_1$ and $p_2$, and we have $a = n$ modulo $p_1$ and $b = n$ modulo $p_2$, can $n$ modulo $p_1p_2$ be evaluated using $a$ and $b$?
2
votes
3answers
150 views

Prove that $\gcd(1 + a + a^2 +\dots + a^{n-1}, 1+a + \dots +a ^{m - 1}) = 1 + a +\dots+ a^{\gcd(m, n) - 1}$

Let $f(n) = 1 + a + a^2 + \dots + a^{n-1}$ We are required to prove $\gcd(f(n), f(m)) = f(\gcd(m, n))$. Proceed by induction on $n$. The base $n = 1$ is trivial. Assume inductively that for some ...
0
votes
1answer
69 views

Natural number n-Divisibility

The number of natural number $n$ in the interval $[1005,2010]$ for which the polynomial $$1+x+x^2+x^3\dots +x^{(n-1)}$$ divides the polynomial $$1+x^2+x^4\dots+x^{2010}$$ is: I could realize that ...
3
votes
1answer
133 views

The number of zeros in the decimal representation of the factorial of 126

How many zeros are in $126!$ ... the result is $34$. But can I calculate it manually? I have seen How many zeroes are in 100! but I don't think it's helpful.
2
votes
2answers
165 views

a divisibility problem

if $a$ is an integer , such that it is not divisible by 2 or 3, prove that $ 24 $ divides $ a^2+ 23$ . I took cases ,case $1$ : when $a$ is divisible by only $2$ and not $3$ then we can write $a = ...
5
votes
1answer
116 views

Solutions of a cubic diophantine equation in $\mathbb{Z}/p\mathbb{Z}$

Suppose $p\in\mathbb{Z}$ is prime and $p\equiv 1\pmod{3}$. Is there an estimate of the number of solutions of $x^3+y^3=z^3$ in $\mathbb{Z}/p\mathbb{Z}$, preferably using elementary number theory and ...
2
votes
1answer
106 views

Prove that if $gcd(n, m) = 1$, then $gcd(R_n, R_m) = 1$

We will call a number with $i$ consecutive $1$s in its decimal representation a repunit and denote it by $R_i$. Prove that if $gcd(n, m) = 1$, then $gcd(R_n, R_m) = 1$. This looked like a proof by ...
12
votes
1answer
498 views

Diophantine equation involving prime numbers : $p^3 - q^5 = (p+q)^2$

Find all pairs of prime nummbers $p,q$ such that $p^3 - q^5 = (p+q)^2$. It's obvious that $p>q$ and $q=2$ doesn't work, then both $p,q$ are odd. Assuming $p = q + 2k$ we conclude, by the equation, ...
1
vote
2answers
70 views

Integer outputs of $y=x^2$ , do their last digits form an irrational?

Let the domain of $y=x^2$ be the positive integers. I input consecutive positive integers from $[1, \infty)$ their last digits are $a, b, c, ...$ respectively. If I then make the number $z=\frac ...
4
votes
1answer
98 views

Does there exist a constant $\sqrt[4]{2} < A < \sqrt2$ such that $\lfloor A^{2^n} \rfloor$ is a practical number for all $n \in \Bbb Z^+$?

Does there exist a constant $\sqrt[4]{2} < A < \sqrt2$ such that $\lfloor A^{2^n} \rfloor$ is a practical number for all $n \in \Bbb Z^+$? I know we can exclude the range ...
0
votes
2answers
97 views

How to prove that the Fibonacci sequence $7\mid U_m\Longrightarrow 8\mid m$ and $4\mid U_m\Longrightarrow 6\mid m$

How to prove that the Fibonacci sequence $$7\mid U_m\Longrightarrow 8\mid m$$ and $$4\mid U_m\Longrightarrow 6\mid m$$I was confused because there $\{ 4,7 \}$ in Fibonacci sequece
2
votes
1answer
43 views

Differentiating between prime/semi-prime and other integers

Does there exist a test that checks if a number is prime or a semi prime in polynomial time? I am aware that AKS can be used to check primality but what about semi primality? ...
1
vote
0answers
71 views

Quadratic Diophantine Primality Testing

Define a 2-Quadratic Group Operation as the following: A 2nd degree polynomial of the form: $$a_1x_1 + a_2x_2 + a_3x_1^2 + a_4x_2^2 + a_5x_1x_2 $$ Define a primal 2-quadratic group number as an ...
2
votes
3answers
88 views

Prove that for all odd $n$, there is an $m$ such that $2^m - 1$ is divisible by $n$

I've been trying to solve a problem that reads as such Prove that for all odd positive integers $n$, there exists a positive integer $m$ such that $(2^m) - 1$ is divisible by $n$. Proof by ...
1
vote
4answers
392 views

Rational solutions for $x^2+y^2=3$

Are there any rational numbers $x$ and $y$ such that $x^2+y^2=3$. I think there are no rational solutions, but I haven't been able to prove it.
1
vote
1answer
449 views

Ruler Function definition and graphical representation

I was just wondering if anyone would be able to explain what the Ruler Function is and how the sequences of numbers it generates. More specifically, I want to know how the function draws the markings ...
1
vote
3answers
90 views

Elementary number theory question [closed]

Let $a^n$ be an integer number for some $n$ such that $a$ a rational number. Why $a$ must be integer?
2
votes
1answer
45 views

If $(m,n)\in\left(\mathbb{N}^*\right)^2$, is there $(j,k,r)\in\left(\mathbb{N}^*\right)^3$ such that $\;r>\max(m,n)$ …

If $(m,n)\in\left(\mathbb{N}^*\right)^2$, is there $(j,k,r)\in\left(\mathbb{N}^*\right)^3$ such that : $\;r>\max(m,n)$ $\; , \;$ $\gcd(10,r)=1$ , $10^j\equiv m\mod r\;$ and $\;10^k\equiv n\mod r$ ? ...
1
vote
2answers
57 views

application on L.C.M and G,C,F

Please I need help on the following problem: The L.C.M and G.C.F of numbers x,18 and 60 are 360 and 6 respectively. What will be the value of x? I know how to find in the case when given two numbers , ...
2
votes
1answer
115 views

Least divisor of a number starting from a certain threshold

So I'm going through The Haskell Road to Logic, Math, and Programming and for the first problem I am already really confused. This function LDF is supposed to be: ...
2
votes
1answer
91 views

This correct this demonstration of Number theory (binomial Expressions)

$$\\$$Em minha apostila tem as demonstrações dos seguintes lemas:$$\text{Lema (*): Sejam $a,m,n,q,r\in\mathbb{N}$ com $a\geq2$ tais que $m=nq+r$ then:}\\(a^m-1,a^n+1)=\begin{cases}(a^n+1,a^r-1)& ...
4
votes
1answer
959 views

Formula for reversing digits of positive integer $n$

I was able to work out the cases for $n$ having up to $4$ digits and was wondering if someone could verify my generalization to $m$ digits. Here I am assuming that when a reversal results in there ...
1
vote
1answer
104 views

Critique on a proof by induction that $\sum_{i=1}^n i^2= n(n+1)(2n+1)/6$?

I need to make the proof for this 1:$$1^2 + 2^2 + 3^2 + ... + n^2=\frac{(n(n+1)(2n+1))}{6}$$ By mathematical induction I know that, If P(n) is true for $n>3^2$ then P(k) is also true for k=N and ...
7
votes
3answers
226 views

$ \exists a, b \in \mathbb{Z} $ such that $ a^2 + b^2 = 5^k $

I saw this problem recently and found an elegant solution to it, and was curious to see if anybody would think of something else. Nice solutions to nice problems are fun to see! Problem: Prove ...