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

learn more… | top users | synonyms (1)

2
votes
2answers
29 views

Computing the volume of a fundamental domain of a lattice

Suppose I have $n$ linearly independent vectors in $\mathbb{R}^m$, say $v_1, .., v_n$. Then $v_1,..., v_n$ form a lattice $\Lambda$ inside a subspace $V$ = $\mathbb{R}v_1 + ... + \mathbb{R}v_n ...
1
vote
1answer
28 views

Why is determinant called volume of the fundamental parallelepiped in geometry of numbers?

Let $v_1, ..., v_n$ be $n$ linearly independent vectors in $\mathbb{R}^n$. Then they form a lattice $\Lambda \subseteq \mathbb{R}^n$ and the volume of the fundamental domain is $|\det A|$, where $A$ ...
1
vote
1answer
25 views

Prove that $z^2 \equiv ab$ mod $p$ is solvable if and only if both or neither of $x^2 \equiv b$ mod $p$ are solvable.

Suppose the $p$ is an odd prime not dividing $ab$. Prove that $z^2 \equiv ab$ mod $p$ is solvable if and only if both or neither of $x^2 \equiv b$ mod $p$ are solvable. I have no idea how to prove ...
0
votes
1answer
38 views

Prove the multiplicity property for $n!$ [duplicate]

I was given this hint in a different problem, Now use that a prime $p$ occurs in $n!$ with multiplicity exactly $\lfloor n/p\rfloor + \lfloor n/p^2\rfloor + \lfloor n/p^3\rfloor + \lfloor ...
0
votes
2answers
58 views

Evaluate this finite product

$$\prod_{n=0}^{99} 2n + 1$$ I tried with partial products but I have no clue. Can I be given a hint?
3
votes
3answers
67 views

Find the largest $k$ such that $3^k$ divides the product of the first $100$ odd integers

Let $P$ be the product of the first 100 positive odd integers. Find the largest integer $k$ such that $P$ is divisible by $3^k$. There are $50$ odd numbers and $50$ even numbers between $0$ and ...
2
votes
2answers
42 views

Use Euclid's algorithm to find the multiplicative inverse $11$ modulo $59$

I was wondering if this answer would be correct the multiplicative of $11$ modulo $59$ would be $5$ hence $5\cdot11 \equiv 4 \pmod{59}$. Is this correct?
0
votes
1answer
26 views

Is sum of all divisors each multiplied by it's respective totient for a particular number is multiplicative when two numbers are coprime?

Is the formula for nth term of sequence http://oeis.org/A057660 is multiplicative when the numbers are coprime ? If yes how to prove it? And what is the answer when they are not coprime.
0
votes
4answers
49 views

using Fermat's little Theorem to find the least residue of $5^{38}\ mod\ 13$

please help me work this out i have no clue thanks Using Fermat’s little theorem, find the least residue of $5^{38}$ modulo $13$.
5
votes
3answers
112 views

Move the last two digits in front to multiply by $6$

Here is the problem: Can you determine the smallest natural number $N>0$ not divisible by $10$, such that when you move the last two digits of $N$ to the front, shifting the other digits two ...
3
votes
4answers
236 views

Writing numbers as a sum of 2s and 3s

Is there a way to count the number of ways a positive integer N, can be written as a sum of twos and threes? Are there any patterns? Re-arranging the twos and threes are distinct..(makes sense right?? ...
0
votes
1answer
21 views

Fraction Transforms

Here's a number theory problem I'm having some difficulty with: Say we transform a fraction by the following rule: we start with some fraction $\frac{m}{n}$ with $m > n$ and then convert it to ...
2
votes
2answers
54 views

Solving the congruence $2x^3 - 3x^2 + 1 \equiv 0 \pmod{49}$

I'm trying to solve the congruence $f(x) = 2x^3 - 3x^2 + 1 \equiv 0 \pmod{49}$. I wrote $f(x)=(x-1)^2(2x+1)$, and I found that it has eight solutions. One solution is $24$, and the others are of the ...
1
vote
2answers
49 views

For a primitive Pythagorean triple $(a, b, c)$, is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?

Let $(a, b, c)$ be a primitive Pythagorean triple. I know that $\gcd(a,b,c) = 1$. Is it always true that $\gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1$?
6
votes
4answers
264 views

A big “smallest” number

What is the smallest natural number $N$ such that moving the last digit to the front one gets the number $9N$? In other words, find the least $N$ such that if $N$ has decimal expansion $abc...xyz$, ...
0
votes
1answer
46 views

How many special kind of numbers are there which are less than $M$?

Natural numbers $n$ such that $N = p\times n^3 + h$ ends in $n$ for a prime $p$ and $0 ≤ h < p$ are called h-trimorphic ($5$ is $0$-trimorphic for all odd $p$). How many $7$-trimorphic less than ...
0
votes
1answer
24 views

Local Rings, How to prove Z/(P^l)Z is a local ring

please do me a great favor to answer my following question: Is the ring Z/(P^l)Z a local ring? If it 's the case what is its maximal principal ideal ?
0
votes
0answers
44 views

Collatz algorithm generalization try-out (Collatz k-algorithm)

Recently I have been reading about the Collatz conjecture here in Mathematics Stack Exchange, and also found the fantastic paper of professor Lagarias about it. Everything was so interesting (and I ...
4
votes
1answer
47 views

Quadratic bound for prime numbers

I once found the following problem meant to be solved at high-school level (some olympiad-level exercise, I guess), and I have never been able to prove it using elementary methods. Does anybody know a ...
1
vote
1answer
44 views

Give an alternative proof of Wilson's theorem ($g$ is a primitive root modulo an odd prime $p$)

Show that $(p-1)! = g^{\sum _{k=0}^{p-1} k}$, where $g$ is a primitive root modulo an odd prime $p$, the use it to give an alternative proof of Wilson's theorem. I was thinking that ${\sum ...
1
vote
1answer
37 views

Proving a property of Pythagorean Triples

I was wondering if there exists a proof showing that there exists no Pythagorean Triple such that when its bases are swapped with the exponents the left and right hand side of the Pythagorean Triple ...
2
votes
2answers
37 views

Solving an inequality $B<n!$ without a calculator or gamma function?

Is there a way to solve $B<n!$ where $B$ is some very large real number (suppose for example $B=10^{17}$) without a calculator or gamma function? At the very least, to find the nearest integer for ...
0
votes
2answers
41 views

greatest common divisor of 4 integers

I've come up with this question in a programming book, and couldn't figure it out : Given four positive integers $a, b, c$ and $d$, explain what value is computed by $\gcd(\gcd(a, b), ...
0
votes
2answers
26 views

Problem in proof of: Show the order $d$ of $a$ modulo $m$ exists and $d\mid\phi(m)$

Theorem: Let $m\in\mathbb{N}$ and $a\in\mathbb{Z}$ satisfy $(a,m)=1$. Then the order $d$ of $a$ modulo $m$ exists, and $d\mid\phi(m)$. Proof: By Euler's theorem, one has $a^{\phi(m)}\equiv ...
2
votes
1answer
56 views

Number Theory : Is a complete residue system modulo $n$ a group?

I was working my way through some basic number theory problems, when in the chapter on "Introduction to Group Theory," I came across the following: Show that for every positive integer $n$, the ...
-2
votes
1answer
85 views

Is 0.9999… equal to -1?

I read the following in a wikipedia article about 0.9999...: A third derivation was invented by a seventh-grader who was doubtful over her teacher's limiting argument that $0.999... = 1$ but was ...
21
votes
2answers
2k views

What is the next perfect square of the form 14444… in decimal notation?

We know that $12^2 = 144$ and that $38^2 = 1444$. Are there any other perfect squares in the form of $\frac{13}{9} (10^n - 1) + 1$ (i.e. $1$ followed by $n$ $4$'s), and how would we prove it?
3
votes
2answers
40 views

Find the number of positive integer solutions such that $a+b+c\le 12$ and the shown square can be formed.

Find the number of positive integer solutions such that $a+b+c\le 12$ and the shown square can be formed. $a \perp b$ and $b\perp c$. the segments $a,b,c$ lie completely inside the square as ...
0
votes
1answer
41 views

Number Theory proving questions [closed]

Let $n$ be a positive integer such that $n \equiv 3 \pmod 4$. Prove that $x^2 \equiv -1 \pmod n$ is not solvable for integer $x$.
3
votes
5answers
88 views

Can every perfect square exist as the sum or difference of two perfect squares?

I believe this is trivial and I'm over-complicating it. But can every squared integer be expressed as the sum of two squared integers OR the difference of two squared integers? And is there a proof ...
-1
votes
1answer
39 views

for which odd number n does 503 divide $n^2+1$ [duplicate]

The question is already mentioned in the title: For which odd number n does 503 divide $n^2+1$ $503\cdot q=n^2+1$
0
votes
2answers
58 views

$x^4\equiv-1 \pmod p$ is solvable if and only if $p \equiv 1 \pmod 8$ or $p=2$

Prove that $x^4\equiv-1 \pmod p$ is solvable if and only if $p\equiv1\pmod 8$ or $p=2$. I was thinking of using cases like for $8m+1$, $8m+2$... in order to prove it but I didn't get anything ...
1
vote
1answer
34 views

$g^p-p$ and $g^p-gp$ are primitive roots modulo $p^2$.

Let g be a primitive root modulo an odd prime p. Then, both $g^p-p$ and $g^p-gp$ are primitive roots modulo $p^2$. I read this question somewhere and the first thing that came to my mind as a ...
1
vote
1answer
36 views

Proving $\frac{p-1}{2}$ is a primitive root modulo $p$ if and only if $2(-1)^{(p-1)/2}$ is a primitive root modulo $p$

Let $p$ be an odd prime. Prove that $\frac{p-1}{2}$ is a primitive root modulo $p$ if and only if $2(-1)^{(p-1)/2}$ is a primitive root modulo $p$. I was thinking that since $\frac{p-1}{2}$ is a ...
3
votes
3answers
57 views

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? [duplicate]

Let $p$ be a prime. Why is ${p^mn \choose p^m}$, where $p \nmid n$, not divisible by $p$? $${p^mn \choose p^m} = \frac{(p^mn)!}{p^m!(p^mn-p^m)!} = ...
5
votes
1answer
57 views

Solving $x^x \equiv x \pmod{17}$.

Momentarily I am studying group of units, and this question seems a bit strange. How could I solve $x^x \equiv x \pmod{17}$?
0
votes
1answer
28 views

$m$th power residue, necessary and sufficient conditions.

Let $n$ be an integer for which $(\mathbb{Z}/n\mathbb{Z})^*$ is cyclic and $a$ is coprime to $n$. Given a positive integer $m$, find the necessary and sufficient conditions for $x^m \equiv a \pmod n$ ...
2
votes
1answer
35 views

If for every k the interval $[a,ak]$ contains $n$ specials numbers how many special numbers $[az,akz]$ must contain?

The purpose of my question is to determine if a specific kind of reasoning is true or false. Let's say that for every positive natural number $a$, there is a at least $n$ "special numbers" in the ...
-2
votes
2answers
28 views

Cardinality of Two Sets

Show that two sets $(0,1)$ and $(a, \infty) $ have the same cardinality. There are proofs all over the Internet, but I do not understand why. I cannot make head or tail of it. Can someone please ...
0
votes
2answers
40 views

Positive solutions of $893x - 2432y = 19$

I am trying to find a solution to $893x - 2432y = 19$ where both $x$ and $y$ are positive integers. When I apply the extended Euclidean algorithm I get a solution where both integers are negative ...
1
vote
2answers
15 views

Why is $\sum_{d\mid p^r}\phi(d)=\sum_{h=0}^r\phi(p^h)$

$\sum_{d\mid p^r}\phi(d)=\sum_{h=0}^r\phi(p^h)$ I read this relation in a proof, but can't work out why it is the case. Thanks in advance for the help.
1
vote
1answer
50 views

Is $p\in\big\{x,…,2x\big\}$ lower-bounding $p\in\big\{x^2,…,(x+1)^2\big\}$?

Is it overreaching or erroneous to consider that possibility? (Alas, I'm not a mathematician, and don't have rigorous language to talk about this.) What I want to say is: Given any even span of ...
1
vote
1answer
87 views

Existence of integer.

Let $a,b,c$ be three integers whose greatest common divisor is $1$ (ie $\gcd(a,b,c)=1$). Show that there exist integers $m$ and $n$ such that $a+mc$ and $b+nc$ are coprime. Progress: I believe the ...
2
votes
1answer
36 views

Show mn has order $2^c$ mod p

Let p be an odd prime such that p doesn't divide mn and each $m,n$ has order $2^d$ modulo p, where $2^d|p-1$. Prove that $mn$ has order $2^c$ modulo p, where $0 \le c\le d-1$. So $(2^d,p) = 1$ and ...
0
votes
1answer
48 views

Assuming $g$ is a primitive root modulo a prime $p$, show that $p-g$ is a primitive root if and only if $p \equiv 1 \pmod 4$.

Assume $g$ is a primitive root modulo a prime $p$. Show that $p-g$ is a primitive root if and only if $p \equiv 1 \pmod 4$. I am studying for a number theory exam that is why I am posting a lot ...
5
votes
4answers
92 views

Prove $2015$ divides $1^{2015}+2^{2015}+3^{2015}+\cdots+2015^{2015}$. [closed]

How to prove that the number $$1^{2015}+2^{2015}+3^{2015}+\cdots+2015^{2015}$$ is divisible by $2015$.
2
votes
1answer
54 views

Show that if n has primitive roots then

Let $$P_{n}=\prod_{1\le a\le n ,(a,n)=1}a $$ Show that if n has primitive roots then $P_{n}=-1$(mod n).Otherwise $P_{n}=1$(mod n). How do I approach this one? It seems interesting.
0
votes
2answers
43 views

What is the primitive root of the following

I happen to find some interesting questions relating primitive roots. If $g^k$ is a primitive root modulo $p$ then so is $g$. I was thinking that we could say that $(g^k)^{(p-1)}=1\pmod p$ since ...
0
votes
5answers
62 views

Prove that if $m$ and $n$ are integers and $mn$ is even, then $m$ is even or $n$ is even.

I have this assignment: Prove that if $m$ and $n$ are integers and $mn$ is even, then $m$ is even or $n$ is even. How should I begin?