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

learn more… | top users | synonyms

3
votes
3answers
758 views

Show that the product of the $\phi(p-1)$ primitive roots of $p$ is congruent modulo $p$ to $(-1)^{\phi(p-1)}$

If $p$ is a prime, show that the product of the $\phi(p-1)$ primitive roots of $p$ is congruent modulo $p$ to $(-1)^{\phi(p-1)}$. I know that if $a^k$ is a primitive root of $p$ if ...
3
votes
2answers
62 views

Solve $k_1 a = k_2 b + c$

Find all $k_1, k_2$ that satisfy $k_1 a = k_2 b + c$ where everything are integers. It feels like there should be some easy way to describe this in terms of congruence and gcd.
4
votes
3answers
136 views

$(a+b+c)^p-(a^p+b^p+c^p)$ is always divisible by…?

$(a + b + c)^p - (a^p + b^p + c^p)$ is always divisible by (a) $p - 1\quad$ (b) $a + b + c\quad$ ( c ) $p\quad$ ( d ) $p^2 - 1$ $p$ is prime I am able to solve this by substituting values ...
1
vote
1answer
176 views

Irrational distances, rational area triangles

Given any positive integer $n\ge3$ how to show that there are $n$ distinct points in the plane such that 1- the distance between any two points is irrational number and 2- each set of three points ...
2
votes
2answers
84 views

Condition(s) that satisfy this equality

I am having difficulty understanding how my book came up with this answer. Define $a \star b =ab+2b$, and suppose $x \star y = y \star x$. Then which of the following must be true? A. ...
2
votes
3answers
265 views

When is $(6a + b)(a + 6b)$ a power of two?

Find all positive integers $a$ and $b$ for which the product $(6a + b)(a + 6b)$ is a power of $2$. I havnt been able to get this one yet, found it online, not homework! any help is appreciated ...
5
votes
3answers
236 views

Further reading on the $p$-adic metric and related theory.

In his book Introduction to Topology, Bert Mendelson asks to prove that $$(\Bbb Z,d_p)$$ is a metric space, where $p$ is a fixed prime and $$d_p(m,n)=\begin{cases} 0 \;,\text{ if }m=n \cr ...
3
votes
1answer
261 views

$\alpha x^2+\beta y^2=\gamma$ solvable over $\mathbb Q$ iff $ax^2+by^2=z^2$ solvable over $\mathbb Z$ with coprime $x,y,z$?

I want to understand an algorithm from [1] to solve $$\alpha x^2+\beta y^2=\gamma \text{ over } \mathbb{Q}$$ with $\alpha, \beta, \gamma\in\mathbb{Q}$. As far is I understood the process the ...
0
votes
0answers
65 views

Calculating A from this equation

I am having trouble with the following question If A and B are positive integers and $A^2 + B^2 = 36$ Then what is $A$? The choices are 6, 7, 8, 9, or 10. How does one show that answer ...
3
votes
2answers
1k views

Prove three things related to the GCD

I have to demonstrate this three formulae: $\gcd(ac,bc)=c\gcd(a,b), \forall a,b,c \in \mathbb{N}$ $a\mid c \land b\mid c \land \gcd(a,b)=1 \implies ab\mid c$ $\gcd(a,b,c)=xa+yb+zc, \forall ...
1
vote
2answers
210 views

Recursive digit-sum

Let the recursive digit-sum(R.D.) be defined as: continue taking the sum of digits until it becomes <10. For example, the digit-sum of 5987 = 29, the digit-sum of 29 =11 So, R.D. of 5987 is 2. ...
1
vote
1answer
272 views

Algorithm for generating an ordered list of pair products

For problem 4 in the euler project part of the assignment is to generate a list of products of 3-digit numbers. The easy way is to just do a cartesian product (I think it's called), and after that ...
-4
votes
2answers
106 views

Find third value

I have a very simple problem but I feel like I am brain-dead. I cant figure it out how to calculate this in Java: 1321 = 0 1771 = 640 1500 = ? Thanks. Edit: ...
1
vote
3answers
88 views

if $ax \equiv 1 \pmod{y}$ and $by \equiv 1 \pmod{x}$, then gcd$(x,y)=1$

I don't think someone has posted this question yet. One looks similar, but I wasn't sure. Sorry in advance if it is. I think I am making things up toward the end. I wanted to make a squeeze ...
2
votes
2answers
57 views

if $ax+by = d$, then $a'x+b'y=d$ where $x>0$ and $0 \leq b' \leq x$

I've been trying this for a little while now, if $ax+by = d, \ $ then $a'x+b'y=d$ where $x>0\ $ and $0 \leq b' \leq x\ $ and $a,b,a',b',x,y, \in \mathbb{Z}$ My first thought is: $$ ...
6
votes
4answers
660 views

Fractional Binomial Coefficients

I recently examined the binomial coefficient $\binom{\frac{1}{2}}{k}$ and found that the denominator was always a power of two. The same is true of $\binom{\frac{1}{3}}{k}$, where the denominator is ...
0
votes
2answers
58 views

Security of a particular cryptosystem

I recently came across this problem, and while I'm fairly certain the solution is not too 'conceptually-challenging', I've been stumped at finding the right trick/manipulation to make any solution ...
7
votes
5answers
355 views

Can $a^2+b^2+2ac$ be a perfect square if $c\neq \pm b$?

Can $a^2+b^2+2ac$ be a perfect square if $c\neq \pm b$? $a,b,c \in \mathbb{Z}$. I have tried some manipulations but still came up with nothing. Please help. Actual context of the question is: ...
5
votes
2answers
126 views

finding all integer $n$ such that $ n\mid2^{n!}-1$

how to find all integer $n$ such that $ n\mid2^{n!}-1$ I find: Of course $2 \nmid n$. We prove that, if $2 \nmid n$ then $n \mid 2^{n!}-1$. $2 \nmid n \iff n = 2k+1 , k \ge 0$, we'll prove: ...
4
votes
3answers
936 views

A problem dealing with even perfect numbers.

Question: Show that all even perfect numbers end in 6 or 8. This is what I have. All even perfect numbers are of the form $n=2^{p-1}(2^p -1)$ where $p$ is prime and so is $(2^p -1)$. What I did was ...
3
votes
1answer
143 views

$a+d=2^k,b+c=2^m$,proving $a=1$

$a<b<c<d$ are odd natural numbers. $ad=bc$ $a+d=2^{k},b+c=2^{m}$ how to prove that $a=1$ I heard that we can prove it by "Four Number Theorem" ,is that right? And is there a different way ...
4
votes
1answer
137 views

If $p$ is a prime and $x,y \in \mathbb{Z}$, then $(x+y)^p \equiv x^p+y^p \pmod{p}$

I want to prove that if $p$ is a prime and $x,y \in \mathbb{Z}$, then $$(x+y)^p \equiv x^p+y^p \pmod{p}$$ So far I know that $$(x+y)^p = \sum_{k=0}^{p} \dbinom{p}k x^{p-k} y^k$$ A part of the above ...
2
votes
2answers
281 views

Given $r$ and $s$ litre jugs, $m$ litres of water can be measured for any positive integer $m$

The problem is: Show that it is possible to measure any integral number of litres using only a $3$ litre and a $7$ litre jug. And then the book says it's true that given $r$ and $s$ litre jugs, ...
0
votes
4answers
181 views

$nx - my = 0$, find smallest positive integer values of $nx$ and $my$ where this is true

My first question on math stackexchange. I have two numbers, $n$ and $m$. Their values will vary but I always know what they are and they're always positive integers (and multiples of 2, but that ...
1
vote
0answers
113 views

How to find the last two digits of $9^{9^{9^9}}$? [duplicate]

Possible Duplicate: The last two digits of $9^{9^9}$ How to find the last two digits of $9^{9^{9^9}}$ (a power tower of 4 $9$'s) ? Is there any special approach to these kind of problems?
34
votes
1answer
1k views

Decomposing polynomials with integer coefficients

Can every quadratic with integer coefficients be written as a sum of two polynomials with integer roots? (Any constant $k \in \mathbb{Z}$, including $0$, is also allowed as a term for simplicity's ...
1
vote
0answers
45 views

A question regarding the method followed in Cohen & Selfridge's paper on covering systems.

Note: I have posted this question on MO before. No one replied, so I am reposting it here. I am reading this paper by Cohen and Selfridge that deals with covering systems. Its link is ...
2
votes
2answers
127 views

showing a quadratic residue

Let $p\equiv3\pmod4$ be prime and $p \nmid x$. How can you show that a quadratic residue modulo $p$ is given by $x$ or $-x$ ? Thanks!
3
votes
1answer
596 views

Change of order of summation.

I feel like an idiot for asking this, so bear my stupidity. I have the sum $\sum_{n\leq N} \sum_{p | n ; \ p \ prime} 1$, and I want to change the order of summation of these two sums I think it ...
1
vote
1answer
97 views

for $n=x^2+3y^2$ , $n=\prod p^{a(p)}$ , $a(p)$ is even for all $p \equiv 2 \pmod 3$ where $p$ is prime

I'd really like your help with the following Number Theory question: I need to show that if I can write an integer $n=x^2+3y^2$ so in the factorization of $n$ to primes, every $p \equiv 2\pmod 3$ ...
3
votes
2answers
340 views

Squares of the form $x^2+y^2+xy$

How can I find all $(a,b,c) \in \mathbb{Z}^3$ such that $a^2+b^2+ab$, $a^2+c^2+ac$ and $b^2+c^2+bc$ are squares ? Thanks !
1
vote
1answer
71 views

Does $k$-th power of $p$ divide ${}_n\!C_r$ if the previous divides $n$?

Does $p^k$ divide ${}_n\!C_r$ for all integer r if $p^k|n$ where $0\leq r \leq n$ and $p$ is prime?
3
votes
4answers
172 views

solving the congruence: $5^n\equiv3^n+2 \pmod{11}.$

I'd really like your help with solving the following congruence: $$5^n\equiv3^n+2 \pmod{11}.$$ I don't know with what to start. Any help? Thanks
6
votes
4answers
1k views

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them. Let $a$ be the primitive root then I know other primitive roots will be among $\{a,a^2,a^3 \cdots\cdots a^{\phi(n)} ...
2
votes
2answers
1k views

Prove/Show that a number is square if and only if its prime decomposition contains only even exponents.

Prove/Show that a number is square if and only if its prime decomposition contains only even exponents. How would you write a formal proof for this.
9
votes
11answers
3k views

If $\gcd(a,b)=1$, then $\gcd(a^n,b^n)=1$

This seems clear, but I don't know how to prove this.. I was trying to show this by induction such that if $a^{n+1}$ = $rs$ and $b^{n+1}$ = $rt$, then $s,t$ are divisible by $a,b$ respectively, but i ...
3
votes
2answers
2k views

Proving that an integer is even if and only if it is not odd

There is this question, but the definition of "even" and "odd" that I am using uses integers instead of just natural numbers; i.e., An integer $n$ is even iff there is some integer $k$ such that ...
1
vote
4answers
179 views

Why is this prime factor not counted

I came across a question: If j is divisible by 12 and 10, is it divisible by 24 ? The example draws the following factor tree which I agree with But then it states that There are only ...
5
votes
0answers
378 views

Digital Numbers using all digits from 1-9

Call a number a digital number if it consists of all the digits from 1-9, each used exactly once. What is the probability that a digital number will be divisible by 7 ? What is the probability that a ...
4
votes
2answers
989 views

the ring $\mathbb Z[\sqrt{-2}]= \{a+b\sqrt{-2} ; a\in \mathbb Z,b\in \mathbb Z \}$ has a Euclidean algorithm

I need to prove that the ring $\mathbb Z[\sqrt{-2}]= \{a+b\sqrt{-2} ; a\in \mathbb Z,b\in \mathbb Z \}$ has a Euclidean algorithm, and to decide whether there are infinitely many primes in this ring. ...
3
votes
3answers
431 views

HCF/LCM problem

Find the greatest number that will divide $x$, $y$ and $z$ leaving the same remainder in each case. Now the solution for this is obtained by finding the HCF of $(x – y)$, $(y – z)$ and $(z – x)$. ...
2
votes
1answer
95 views

Computing the value of $(\frac{p-1}{2})!$ modulo $p$.

I want to prove that for $p \geq 3$, and for $a=(\frac{p-1}{2})!$, if $p \equiv1\pmod 4$, then $a^2\equiv -1 \pmod p$, and if $p \equiv 3\pmod4$, then $a \equiv +/-1 \pmod p$. For the first part, I ...
1
vote
2answers
141 views

Relation Between $(\mathbb{Z}/a\mathbb{Z})^\times$ and $(\mathbb{Z}/ab\mathbb{Z})^\times$

How can we prove that if there exists an element of order $c$ in $(\mathbb{Z}/a\mathbb{Z})^\times$ then there must exist some element of order $c$ in $(\mathbb{Z}/ab\mathbb{Z})^\times$?
4
votes
2answers
264 views

infinite number of irreducible polynomials in $\mathbb{Z}/2{\mathbb Z}[X]$

For $A= \mathbb{Z}/2{\mathbb Z}[X]$ ring of polynomials with coefficient in the field $\mathbb{Z}/2{\mathbb Z},$ I need to show that there are infinite number of irreducible polynomials in $A.$ How ...
3
votes
4answers
1k views

Finding last digit of numbers raised to large powers

This question came in a competitive exam I took recently. The last digit of LCM of $3^{2003} - 1$ and $3^{2003} + 1$ is is there any strategy by which we can quickly determine the answer? I am ...
4
votes
2answers
521 views

Last few digits of $n^{n^{n^{\cdot^{\cdot^{\cdot^n}}}}}$

I want to compute last few digts (as much as possible ) of the following number $$ N:=n^{n^{n^{\cdot^{\cdot^{\cdot^n}}}}}\!\!\!\hspace{5 mm}\mbox{ if there are $k$ many $n$'s in the expression and ...
3
votes
1answer
594 views

if $f(n)$ is multiplicative prove that $f(n)/n$ is also multiplicative.

The question asks that if $f(n)$ is multiplicative to prove that $f(n)/n$ is also multiplicative. This is what I have: So, $f(n)$ is multiplicative means that if $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ ...
5
votes
1answer
151 views

Is there a closed form to this expression?

Consider $$2^{n-1} + 2^{n-2}\dfrac{(n - 1)!}{1!(n - 2)!} + 2^{n-3}\dfrac{(n - 2)!}{2!(n - 2 \cdot 2)!} + 2^{n-4}\dfrac{(n - 3)!}{3!(n - 2 \cdot 3)!} + 2^{n-5} \dfrac{(n - 4)!}{4!(n - 2 \cdot 4)!} + ...
7
votes
2answers
137 views

Under what conditions does $(\frac{3}{p})(\frac{-1}{p})=1?$ Two ways, different results.

I have quite a problem, two methods, different results. something's wrong. I'm trying to find under what conditions the Legendre symbol for $(\frac{3}{p})(\frac{-1}{p})=1$. First Way: ...
12
votes
1answer
710 views

Sum of powers and prime numbers

I'm not able to find solutions of the following equation: $$2^k+3^k=p$$ where $p$ is a prime number and $k \in N$. It's easy to show that we have a solution when $k=1,2,4$. Is it possible to find any ...