# Tagged Questions

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

51 views

### On non-existance square a natural number

let $n$ to be a natural number . Why there is not any integer $q$ such that $$n^2=6q-1.$$ My attempt: If there exists this $q$, then $n$ to be odd integer. Now let $n=2k+1$. Then $4k^2+4k+1=6q-1$. ...
34 views

### Why is $(p-2)! \textrm{ mod } p$ always 1 if $p$ is prime?

After running some test on my computer I found that when you have a prime $p$, then $(p-1)! \textrm{ mod } p$ always equals to $p-1$ and that $(p-2)! \textrm{ mod } p$ always equals to $1$. Why is ...
64 views

### Writing a given number as the sum of four triangular numbers

"Every number can be written as the sum of three triangular numbers. Can you prove it?"< this is the problem I have so far that: there are lots of numbers like 5 that cannot be written as the sum ...
35 views

### Show that every $m$ which has the property that $a^{m-1}\equiv1 \pmod m$ for all $a$ with $(a,m)=1$ is square-free

$a^{m-1}\equiv1 \pmod{m}$ for all $a$ with $(a,m)=1$. I was able to prove the first part of the problem: show that for every $a$ such that $(a, 561)=1$, the congruence $a^{560} \equiv 1\pmod{561}$ ...
159 views

### Proving $\sqrt2$ is irrational

I used the method of contradiction by assuming that $\sqrt 2$ is a rational number. Then, by the definition of rational number, there exist two integers $p$ and $q$ whose ratio equals $\sqrt 2$. Thus, ...
126 views

### What is the last digit? [closed]

Consider all 100 digit numbers, i.e., those between $0$ and $10^{100} - 1$ (inclusive). For each number, take the product of non-zero digits (treat the product of digits of $0$ as $1$) , and sum ...
24 views

### Computing $x \pmod 5$ if we only know $x \pmod 7$

Let's say we have a number $n$ of which I know its value $x$ modulo $k$, then how can I calculate its value modulo $l$? For example; $n=271, k=7$, and $l=8$, so $x=271 \textrm{ mod } 7=5$. How can I ...
29 views

### Prove the generalized version of Euler's totient function.If $(a,b)=d$, then $\varphi(ab) = {d\varphi(a)\varphi(b)\over \varphi(d)}$

If $(a,b)=d$, then $$\varphi(ab) = {d\varphi(a)\varphi(b)\over \varphi(d)}$$ I thought about writing out $a, b$ and $d$ in their prime power decomposition, but then wasn't sure how to proceed.
36 views

### Help on understanding this congruency

It is really simple but somehow I cannot connect the dots. If $p$ is an odd prime, how come $-1 \not\equiv 1 \pmod p$ ?
52 views

### Under which circumstances is the sum of $n$ $k$-th powers a $k$-th power?

Consider the sum $s$ of $n$ natural numbers each rised to a certain power $k$: $$s= a_1^k + a_2^k + \cdots + a_n^k.$$ Under which circumstances is $s = b^k$, for some $b \in \mathbb N$?
Let $A_p$ be the set of all numbers whose prime factors are all in first $p$ prime numbers. example: $A_2= \{2,3,4,6,9,12,16,18,\ldots \}$ (all of these numbers can be generated by repeatedly ...