There are only 36 physical address lines but a page table entry is 64
bit long. How does the CPU check if the address is valid?
This is actually done by a piece of hardware called the memory management unit (MMU), which handles virtual-to-physical address translation. In terms of an address being "valid", each process has it's own unique address space (thus implementing a virtual memory scheme), so any address is technically valid. Remember, a process can allocate more memory than is physically available.
The MMU uses a translation lookaside buffer (TLB) to quickly decode the virtual address into a physical one, held within a page table.
How does Linux OS map the same virtual address in different processes
to different physical addresses?
This is again due to each process having a unique virtual address space, which is fundamental for implementing virtual memory. A virtual address for a given process is mapped to some physical storage hardware (RAM, disk, etc...), but the mapping is done at run-time by the operating system & MMU.