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

learn more… | top users | synonyms (1)

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
35 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
55 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
14 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
49 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
47 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}$. [on hold]

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
60 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?
0
votes
2answers
53 views

Show that order of $n^k$

I have seen this everywhere but how do i show that : if $a$ is an element of order $n$ in a group $G$ then the order of $a^k$ is $\frac {n}{(n,k)}$. We know that since a has order n that $a^n = 1$
0
votes
1answer
20 views

PIE Problem with divisors

Find the number of positive integers that are divisors of at least one of $10^{10},15^7,18^{11}$. Let $n(A)$ be the number of positive integers that divide $10^{10}$ let $n(B)$ be the number of ...
2
votes
0answers
28 views

Three Cases Positive Prime Numbers in $\mathbb Z$

What are the first $3$ positive prime numbers $d$ in $\mathbb Z$ such that the quadratic integers in $Q[\sqrt{d}]$ are precisely the ones of the form $a + b\sqrt{d}$, in which $a$ and $b$ are rational ...
1
vote
5answers
33 views

When $p=2$ or $p$ prime, with $p=1\pmod{4}$, $x^2\equiv -1\pmod{p}$ is soluble - trouble understanding proof

Theorem: When $p=2$ or $p$ prime, with $p=1\pmod{4}$, $x^2\equiv -1\pmod{p}$ is soluble Proof: When $p=2$, the statement is clear. Assume $p\equiv 1\pmod{4}$, let $r=\frac{p-1}{2}$ and $x=r!$ Then ...
2
votes
1answer
47 views

Adding mod Values

I have the expression $$\frac{1000}{2^k} - \frac{n \pmod{2^k} + (1000-n) \pmod{2^k}}{2^k}$$ I know that the value of the expression is an integer, and I suspect that it is $$\frac{1000 - \ell \cdot ...
1
vote
4answers
83 views

Prove that if $k \in \mathbb{N}$, then $k^4+2k^3+k^2$ is divisble by $4$

I am trying to solve by induction and have established the base case (that the statement holds for $k=1$). For the inductive step, I tried showing that the statement holds for $k+1$ by expanding ...
1
vote
1answer
14 views

What does it mean by “level sets of $\bar{G}$, a collection of forms, partition those of $\bar{F}$, another collection of forms”

I was reading an article and I was wondering if someone could explain me what a certain phrase meant. Let $\bar{F}$ be a collection of integral forms of degree less than or equal to $d$. And suppose ...
4
votes
1answer
99 views

Why is it called the Fundamental Theorem of Arithmetic?

The Fundamental Theorem of Arithmetic is easy enough to understand, saying that every integer greater than 1 is either prime or is the product of a unique combination of prime numbers. What I don't ...
0
votes
1answer
49 views

Example for $a^k\equiv b^k$ and $k\equiv j$ but $a^j\not\equiv b^j\pmod n$

I need some help in the number theory please , Who can give me an example : If $$a^k≡b^k \pmod{n}$$ and $$k≡j \pmod{n}$$ is not necessary to be $$a^j≡b^j \pmod{n}$$
0
votes
1answer
53 views

$a^2\equiv1 \pmod n$ iff $a\equiv\pm\,1\pmod p$ for all $p\mid n$

(Not)if $a$ is an integer and $n$ a postive integer, then $a\equiv\pm 1\pmod p$ for all primes dividing n if and only if $$a^2\equiv 1\pmod n$$ $\Longrightarrow $ is wrong,Tonyk note ...
2
votes
3answers
130 views

Integer solutions to $x^{x-2}=y^{x-1}$

Find all $x,y \in \mathbb{Z}^+ $ such that $$x^{x-2}=y^{x-1}.$$ I can only find the following solutions: $x=1,2$. Are there any other solutions?
1
vote
1answer
24 views

Show that if $f,g:\Bbb{N}\to \Bbb{C}$ are multiplicative, then so is $f*g(n)=\sum_{d|n}{f(d)g({n\over d})}$. [duplicate]

Show that if $f,g:\Bbb{N}\to \Bbb{C}$ are multiplicative, then so is $f*g(n)=\sum_{d|n}{f(d)g({n\over d})}$. What I did is: Let $m$ and $n$ be co-primes. $m's$ divisors=$\{1,m_1,...,m_s,m\}$, $n's$ ...
9
votes
1answer
77 views

Solving a Diophantine equation: $p^n+144=m^2$

I found this Diophantine equation: $$p^n+144=m^2$$ where $m$ and $n$ are integers and $p$ is a prime number. I solved it but I want to know if there exist other proofs through the use of rules of ...
1
vote
1answer
45 views

How many non-negative integral solutions?

How many non-negative integral solutions does this equation have? $$17x_{17}+16x_{16}+ \ldots +2x_{2}+x_1=18^2$$ I add some conditions that bring more limitations: $$\sum_{i=1}^{17}x_{i}=20 \quad 0 ...
1
vote
0answers
16 views

Show that the number of steps of the Euclidean algorithm is less than $2\log_2{b}$.

Show that the number of steps of the Euclidean algorithm is smaller than $2\log_2{b}$ where $b\ge a$. Before you dismiss the question as a copy, I have crucial questions, not answered in another ...
1
vote
1answer
30 views

Finding a natural number $k>1$ such that $k$ divides $(26+35n)$ and $(3+7n)$

I am trying to find a natural number $k>1$ such that $k$ divides $(26+35n)$ and $k$ divides $(3+7n)$ for some integer $n$. I know that $(ka)=(26+35n)$ for some $a \in Z$ and $(kb)=(3+7n)$ for some ...
1
vote
1answer
23 views

Is there exist $n_p\in\mathbb{N}$ such that $p+1\equiv 0 \mod (4n_p-p)$ for prime $p(\ge 5)$?

I am looking a proof for, Existence of a positive integer $n_p$ such that $$p+1\equiv 0 \mod (4n_p-p) $$ for each prime $p\ge 5.$ But I have no idea to get an attempt to this problem in general. ...
4
votes
4answers
52 views

Showing $k^2-1$ is divisible by 8 when $k$ is an odd natural number

Prove that $k^2-1$ is divisible by $8$ when $k$ is an odd natural number. I am trying to prove this using induction. Initial case: Let $k\in N$ such that $k=1$ Then $k^2-1=1^1-1=0$. ...
1
vote
2answers
41 views

0 as an element of the natural numbers [duplicate]

For what reasons would or wouldn't one want 0 to be the start of the natural numbers as opposed to 1? Why would one want it to be 1, or why wouldn't one?
1
vote
1answer
17 views

prove a function is not one-to-one

Let us look at the field $\mathbb{F}_{p}=\{0,1,2,...,p-1\}$ for a prime number p. And let $f:\mathbb{F}_{p}\rightarrow \mathbb{F}_{p}$ be the function given by $f(n)=n^2 \space (mod \space p)$. How ...
-1
votes
2answers
51 views

$p\mid F_n$ show the following is true if …

If $p \mid F_n$ for $n > 1$, then $p \equiv 1 \pmod {2^{n+1}}$. Fermat numbers $F_n$ are of the form $F_n=2^{2^n} +1$. So $p\mid 2^{2^n} +1$.
1
vote
4answers
78 views

Prove that if $3|mn$, then $3|m$ or $3|n$

I am trying to prove this for integers $m$ and $n$. I tried to reach prove that $3|m$ by assuming that 3 does not divide $n$, but this is such a basic assumption of mine already that it is hard for ...
3
votes
1answer
35 views

Bounding $x^2+6x$ between consecutive cubes when solving $y^3=x^2+6x$

I am familiar with the method of bounding a polynomial between consecutive squares to prove it is not a square. For example, this method can prove $y^2=x^2+x+1$ has no solutions since ...
2
votes
3answers
48 views

If $x^2\equiv a\pmod n$, then $(n-x)^2\equiv a\pmod n$

Given that $x$ is a solution to $x^{2}\equiv a \pmod n$, show that $y=n-x$ is also a solution. Please don't solve, just give me a hint.
0
votes
1answer
42 views

If $m\mid n$ then $p^m-1\mid p^n-1$ [duplicate]

I know $m$ ,$n$ are two positive integer numbers such that $m\mid n$. If $p$ is a prime number, I want to show $p^m-1\mid p^n-1$.
-1
votes
6answers
81 views

Solve for $x$ in the congruence $2x \equiv 7\pmod{17}$ [closed]

Solve for $x$ in the congruency $2x \equiv 7\pmod{17}$. I know this should be fairly easy.. I just don't know the steps.
5
votes
4answers
50 views

Find $n\bmod 8$ when $n\bmod 56=29$

A number when divided by $56$ gives the remainder $29$. If it is divided by $8$ then what will be the remainder? Sorry if this is a stupid question, but I'm studying to improve my math.
0
votes
1answer
22 views

Show that $n\bmod m$ is periodic $\forall n,m \in \mathbb{N}^+$

How can I show that $n\bmod m$ is periodic? If I have a simple example like $n\bmod6 \equiv a$ how can I show that this is periodic if e.g $f(n) = n\bmod6$?
-1
votes
2answers
58 views

Find remainder of $3^{12} + 5^{12}$ when divided by $13$ [closed]

What is the remainder when $3^{12} + 5^{12}$ is divided by $13$?
1
vote
2answers
85 views

Different formulations of the Law of Quadratic Reciprocity

The law of quadratic reciprocity is given as: $(\frac{p}{q})(\frac{q}{p}) = (-1)^{((p-1)/2)((q-1)/2)}$ Apparently we can say: $(\frac{p}{q}) = (\frac{q}{p})(-1)^{((p-1)/2)((q-1)/2)}$ and ...
1
vote
2answers
36 views

analytical ability and logical reasoning

There are $6561$ balls out of which $1$ is heavy. Find the minimum number of times the balls have to be weighed for finding out the heavy ball. How can I solve this step by step?
0
votes
3answers
31 views

How to formally prove: if $d\mid da+b$, then $d\mid b$?

How would I formally prove that for the integers $a$, $b$, and $d$, if $d\mid da+b$, then $d\mid b$? Would a direct proof be the best option? If I do a direct proof I seem to get stuck pretty ...
1
vote
1answer
23 views

Relative Primes and Congruence

Suppose that $a$ and $n$ are relatively prime. Prove that there is an integer $b$ such that $ab\equiv 1\pmod n$ .