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

learn more… | top users | synonyms (1)

2
votes
1answer
76 views

Why inverse modulo exponentiation is harder than inverse exponentiation without modulo

I am new to number theory. I read in cryptography inverse modulo exponentiation is used because it is hard. But I couldn't understand the advantage of it over inverse exponentiation without modulo. ...
-4
votes
3answers
478 views

why can't we divide by zero ?! [duplicate]

in arabic sites which is interested in maths , i find many topics like ,here is a proof that 0=2 . and we answer that the proof is wrong as we can't divide by zero . but i really wonder , why ...
14
votes
3answers
274 views

Showing that $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$

For any odd positive integer $k\geq1$, the sum $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$. I used induction principle for the solution but cannot prove it. I took $P(k) = ...
1
vote
2answers
91 views

Solving for $a,b,c,d$ where $a^2 + b^2 + c^2 + d^2 = 630^2$

How could one solve for $a,b,c,d$ where: $$a^2 + b^2 + c^2 + d^2 = 630^2,\ a>b>c>d$$ $a,b,c,d$ squared is equal to the square of $630$, and $a$ is larger than $b$, and so forth. $a,b,c,d$ ...
1
vote
0answers
74 views

When is $n!+1$ a square? [duplicate]

I'm looking for the solutions $(n,m)$ of the equation $n!+1=m^2$. I have calculated the values of $\sqrt{n!+1}$ for $n \le $ and found only the solutions $(4,5)$, $(5,11)$ and $(7,71)$. Are these ...
0
votes
1answer
44 views

not able to get the divisor

I faced one issue. The issue is as follows. I want to divide a particular number with 7,9,11 but in every case i want to get the remainder as 1,2 3 accordingly. Could you please help me get the ...
4
votes
1answer
165 views

Number Theory: Determine $a$ and $b$ satisfying divisor relationships

Determine integers $a$ and $b$ such as : $$a|b^2 \text{ and } b|a^2 \text{ and } (a+1) |(b^2+1)$$ I had tried to create a system , but I don't think that is the way to solve this problem Thanks. ...
3
votes
4answers
252 views

What is $2012^{2011}$ modulo $14$?

$$2012^{2011} \equiv x \pmod {14}$$ I need to calculate that, all the examples I've found on the net are a bit different. Thanks in advance!
7
votes
2answers
679 views

Given that $xyz=1$ , find $\frac{1}{1+x+xy}+\frac{1}{1+y+yz}+\frac{1}{1+z+xz}$?

I think I solved this problem, but I don't feel $100$ percent sure of my solution. We have: $xy=\large {\frac 1z}$ $xz=\large \frac 1y$ $yz=\large \frac 1x$ So let's substitute these into our sum: ...
4
votes
1answer
66 views

Symmetry in reduced residue systems

This may be a stupid question, but it looks to me like the reduced residue systems modulo N are symmetrical about N/2; that is to say, that the there is the same number of integers not divisible by a ...
4
votes
2answers
93 views

Prove that $\sum_{i=1}^{m-1} i^k$ is divisible by $m$

Prove that $\sum\limits_{i=1}^{m-1} i^k$ for odd numbers $m,k \in \mathbb{N}$ is divisible by $m$. Because $m \mid m^k$, it is equivalent to the following: Prove that $m \mid ...
6
votes
4answers
296 views

Greatest integer $n$ where $n \lt (\sqrt5 +\sqrt7)^6$

I'm really not sure how to do this. I factored out a power of $3$ and squared so that I have $2^3 (6+\sqrt{35})^3 \gt n$ , and I know that if I can prove that $12^3-1 \le (6+\sqrt{35})^3 \lt 12^3$ I ...
2
votes
1answer
393 views

Peano Axioms natural numbers, total order, uniqueness of addition and multiplication

Could you tell me how to prove the following? $(1)$ There exists the unique operation of addition : $+ \ : \ \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ such that $n+0=n$ and $n+ \sigma(m) ...
0
votes
3answers
130 views

Quadratic residues, mod 5, non-residues mod p

1) If $p\equiv 1\pmod 5$, how can I prove/show that 5 is a quadratic residue mod p? 2) If $p\equiv 2\pmod 5$, how can is prove/show that 5 is a nonresidue(quadratic) mod p?
2
votes
3answers
217 views

If $p$ is congruent to $2 \pmod 3$, how can I prove that all $a$, $1 \le a \le p-1$ are cubic residues $\mod p$?

If $p$ is congruent to $2 \pmod 3$, how can I prove that all $a$, $1 \le a \le p-1$ are cubic residues $\mod p$? Here's what I've done: $1^3$ congruent to $1 \pmod p$ thus, 1 is a cubic residue, ...
8
votes
1answer
290 views

The product of two natural numbers with their sum cannot be the third power of a natural number.

I wanted to know, how can i prove that the product of two natural numbers with their sum cannot be the third power of a natural number. Any help appreciated. Thanks.
1
vote
0answers
50 views

How to build $\operatorname{Hom}(\mathbb{Z}_p^*,\mathbb{Z}_{pq}^*)$ without solving DLP?

For given two distinct primes p and q, I want to construct all homomorphisms from the multiplicative group $\mathbb{Z}_p^*$ to the multiplicative group $\mathbb{Z}_{pq}^*$. Thanks to Jyrki ...
2
votes
1answer
354 views

Prove “casting out nines” of an integer is equivalent to that integer modulo 9

Let $s(x)$ be an abstraction for casting out nines of integer $x$. For all integers $x$, prove $s(x) \equiv x$ mod $9$ I'm not asking for an answer more of a way to attack this problem. Can't think ...
2
votes
2answers
840 views

For $n>3$ show that the integers $n$, $n+2$, and $n+4$ cannot all be prime

Okay so the solution I am given states that the division algorithm $\implies p=3k+1$ or $p=3k+2$ for some $k \in Z$ and $p \neq 3$. Can anyone explain why $p$ has to be $3k+1$ or $3k+2$? I can't ...
0
votes
2answers
39 views

Explanation of this step in a modular arithmetic problem

The multiplicative inverse of $5$ is $7$, when using mod $34$. $$\begin{align*} 5\cdot x&=3\\[0.1in] 7\cdot 5\cdot x &=7\cdot 3\\[0.1in] 1\cdot x &=7\cdot 3\\[0.1in] x&=21 ...
1
vote
0answers
69 views

Simplify $\frac{[m+n-1]!}{[m]![n]!}$ where $[k]=x^k-x^{-k}$ and $[k]!=[2][3]…[k]$.

Adopting the notation $[k] = x^k - x^{-k} $ and $[k]! = [2][3]...[k]$ (note that $[1]$ is omitted), and letting $m,n$ be two integers greater than $1$ such that $n>m$ and $gcd(m,n)=1$, would it be ...
5
votes
2answers
258 views

can all triangle numbers that are squares be expressed as sum of squares

I'm not sure if this is just a subset of Which integers can be expressed as a sum of squares of two coprime integers? which in turn points to ...
1
vote
2answers
68 views

How many divisors can $bx$ have, given the number of divisors of $b$ and $x$?

May I ask you for a little help about a problem from number theory: The numbers $x$ and $b$ have exactly 15 resp. 3 divisors. How many divisors could the numbers i) $ 7x$, ii) $ 6x$, iii) $ ...
10
votes
2answers
646 views

Factoring a number of complex integers?

Say you are given a number (ex: $377$) and you express it in a form that allows you to factor it over the complex integers: Notice, $377 = 16^2 + 11^2$ Thus: $(16 + 11i) $ and $(16 - 11i)$ Are ...
6
votes
3answers
818 views

Derivation of Pythagorean Triple General Solution Starting Point:

I was reading on proof wiki about the derivation of the general solution to the pythagorean triple diophantine equation: $$ x^2 + y^2 = z^2, $$ where $x,y,z > 0$ are integers. I came across the ...
4
votes
4answers
249 views

Mathcounts 2013 state sprint round #14

How many ways can all six numbers in the set $\{4, 3, 2, 12, 1, 6\}$ be ordered so that $a$ comes before $b$ whenever $a$ is a divisor of $b$?
3
votes
0answers
405 views

Confusing proof of brun's theorem?

I read Brun's proof of Brun's theorem here : http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f110.image (and the following pages) and here http://gallica.bnf.fr/ark:/12148/bpt6k486270d/f138.image ...
1
vote
2answers
127 views

What topics to include on a first course in number theory

I need to teach a course in elementary number theory next academic year. What topics should be included on a first course in this area? What is best order of doing things? The students have a minimum ...
2
votes
1answer
78 views

simple congruence with large power and large moduli

I am trying to compute $2^{111455} \pmod{2012}$, but since the numbers are too large, I don't know how to compute it efficiently. I've got: $2012=2^2 \times 503$, $503$ is a prime. And that ...
0
votes
2answers
97 views

Smallest $k$ such that $4900$ divides $600k$

(A) Express 600 as the product of its prime factors. (B) Given $4900=2^2 \cdot 5^2 \cdot 7^2$, find the highest common factor of $600$ and $4900$ (C) Given that $600k$ is a multiple of ...
1
vote
1answer
105 views

Complex numbers in Pell's equation

I have a question about complex numbers (a+ib) and (c+id) as solutions to Pell’s equation, with a to d natural non-zero numbers. $(a+ib)^2 –n (c+id)^2 =1$ implies that $2iab=n2icd$ and therefore ...
1
vote
0answers
48 views

$\operatorname{Prob}\limits_{x,y\in\mathbb{Z}_q^*}[\gcd(xy \bmod q, pq)>1: \gcd(x,pq)=\gcd(y,pq)=1]=?$

For given two distinct odd primes $p$ and $q$, how to count the probability $$\operatorname{Prob}\limits_{x,y\in\mathbb{Z}_q^*}[\gcd(xy\bmod q, pq)>1: \gcd(x,pq)=\gcd(y,pq)=1]=\, ?$$
1
vote
1answer
89 views

Is there other homomorphisms from $\mathbb{Z}_q^*$ to $\mathbb{Z}_{pq}^*$?

For given two distinct primes p and q, is there other homomorphisms from the multiplicative group $\mathbb{Z}_q^*$ to the multiplicative group $\mathbb{Z}_{pq}^*$, except the following two maps: ...
1
vote
1answer
106 views

Is there non-trivial homomorphism from $\mathbb{Z}_q^*$ to $\mathbb{Z}_p^*$?

For two distinct primes $q$ and $p$, is there non-trivial homomorphism from $\mathbb{Z}_q^*$ to $\mathbb{Z}_p^*$? Here, $\mathbb{Z}_q^*$ and $\mathbb{Z}_p^*$ mean the multiplication groups with ...
1
vote
1answer
88 views

existence of a prime $p$ for which $a$ is a primitive root

It is known that every prime $p$ has a primitive root modulo $p$. Is every number $a$ which is not a perfect square a primitive root modulo $p$ for some prime $p$? If it is a square, we already have ...
4
votes
3answers
271 views

If a prime $p$ is divided by 30, remainder is either prime or 1

Show that if a prime number $p$ is divided by 30, then the remainder is either a prime or 1. I did the sum sum but cannot complete it. I took $p=6k+1$ and $p=6k-1$ form. now for any $k=5m$ we get ...
4
votes
2answers
232 views

Criterion for sum/difference of unit fractions to be in lowest terms

Pick two nonzero integers $a$ and $b$, so $(a,b)\in (\mathbb{Z}\setminus\{0\})\times(\mathbb{Z}\setminus\{0\})$. We want to add the fractions $1/a$ and $1/b$ and use the standard algorithm. First ...
1
vote
1answer
255 views

Question - Möbius inversion formula

I need your help in the next question: Prove directly from the definition the Möbius inversion formula. (Möbius function defined as follows: μ(n) = 1 if n is a square-free positive integer with ...
1
vote
1answer
727 views

Evaluating $\sum_{i=0}^{m-1} [ \frac{b + ia}m ]$

Let $a,b\in\mathbb{Z}$ and $m\in\mathbb{Z}_{>1}$ Evaluate $[\frac {b}{m}] + [\frac {(b+a)}{m}]+ [\frac {(b+2a)}{m}]+ [\frac {(b+3a)}{m}]+ [\frac {(b+4a)}{m}]+ [\frac {(b+5a)}{m}]+.....+ [\frac ...
5
votes
1answer
147 views

In a sequence of $n$ integers, must there be a contiguous subsequence that sums to a multiple of $n$?

Let $x_1, \ldots, x_n$ be integers. Then are there indices $1\le a\le b\le n$ such that $$\sum_{i=a}^b x_i$$ is a multiple of $n$?
2
votes
1answer
30 views

Find out the position of an element in a loop according to the number of elements

First of all, I am terrible at math, and this small problem is giving me a nice headache. I'm sure most here will see this as an easy solution. I will try to be as clear as possible. I have X ...
0
votes
1answer
107 views

Show that if $n$ and $k$ are positive integers, then $\lceil \frac{n}{k} \rceil = \lfloor \frac{n - 1}{k} \rfloor + 1$

This is answer in the back of the book but it doesn't make sense to me: There is some $b$ with $(b-1)k < n \leqslant bk$. Hence, $(b-1)k \leqslant n-1 < bk$. Divide by $k$ to obtain $b-1 < ...
2
votes
2answers
147 views

Euler-Fermat Theorem

So I am trying to teach myself number theory, and while trying to work on some exercises I got stuck trying to prove that, for all $n \in \mathbb{Z}$, $$ n^{91} \equiv n^{7} \bmod 91 $$ What I first ...
5
votes
0answers
277 views

Maximum length of sequence of non-coprimes of $N$ - least upper bound for Jacobsthal's function

I am looking at the length of the longest sequences of adjacent integers that are not coprime to $N$ for very large $N$. Let $F_N$ be the set of integers less than $N$ which are not coprime with $N$: ...
3
votes
1answer
125 views

$x^4+5y^4=z^2$ doesn't have an integer solution.

I hope to show that $x^4+5y^4=z^2$ doesn't have an integer solution. You may guess that you can solve it using the infinite descent procedure. I tried it but I had a trouble in solving it. What I ...
19
votes
3answers
617 views

Prove $n\mid \phi(2^n-1)$

If $2^p-1$ is a prime,(thus $p$ is a prime,too) then $p\mid 2^p-2=\phi(2^p-1).$ But I find $n\mid \phi(2^n-1)$ is always hold, no matter what $n$ is.Such as $4\mid \phi(2^4-1)=8.$ If we denote ...
0
votes
2answers
83 views

Given n numbers, prove that difference of at least one pair of these numbers is divisible by n-1

Suppose you have a list of $n$ numbers, $n\geq 2$. Let $A$ be the set of differences of pairs of the $n$ numbers. Prove or disprove that at least one element of A must be divisible by $n-1$. Anyone ...
2
votes
2answers
104 views

How many even number in a sequence are there?

How many even numbers in the below numbers ? $$\binom{k}{0},\binom{k}{1},\binom{k}{2},\ldots,\binom{k}{k}$$ Worng: Is it true that all of them are odd iff $k$ is odd, and if $k$ is even then ...
2
votes
1answer
123 views

How many integer solutions to this 5 integers equation?

Ref to the question in Unusual 5th grade problem, how to solve it. Find a positive integer solution $(x,y,z,a,b)$ for which $$\frac{1}{x}+ \frac{1}{y} + \frac{1}{z} + \frac{1}{a} + \frac{1}{b} = ...
2
votes
1answer
134 views

kaleidoscopic effect on a triangle

Let $\triangle ABC$ and straightlines $r$, $s$, and $t$. Considering the set of all mirror images of that triangle across $r$, $s$, and $t$ and its successive images of images across the same ...